| [ QuizWit ] in KIDS 글 쓴 이(By): memory (라면밥말아) 날 짜 (Date): 2006년 8월 29일 화요일 오후 01시 05분 53초 제 목(Title): Re: [Q] NP=Co-NP문제 참고로 P=NP then NP=CoNP는 쉽게 풀리는 같습니다... P=NP라고 가정하고 A는 NP에 속해엤다면 A는 또한 P에 속하겠죠 P=NP니까 그리고 A가 P에 있으니까 A에 있는 어떤 것도 poly time안에 결정할 수 있습니다. 단순히 A의 decider의 결과를 바꿔서 complement를 구할 수 있고 이걸로 bar_A를 poly time안에 구할 수 있겠죠. 그러므로 bar_A도 P에 있구요. 위에 P=NP니까 bar_A도 NP에 속하겠고 CoNP의 정의대로 If bar_A가 NP에 있면 A도 CoNP에 있으니까 NP=CoNP이다.. 근데 저걸 순서를 바꿔놓으면 증명을 못하겠네요.. |