| [ QuizWit ] in KIDS 글 쓴 이(By): memory (라면밥말아) 날 짜 (Date): 2006년 8월 29일 화요일 오후 12시 59분 25초 제 목(Title): [Q] NP=Co-NP문제 Show that if Np is closed under complement then P=NP. 혹시 푸실 수 있는 분 계시나요? 워낙 한국사람들이 싫어하는 분야라 물어봐도 답이 잘 안나오네요 대강 보면 NP가 complement에 닫혀있다면 어떤 NP에 속해있는 어떤 랭귀지 L에 대해 그것이 complement인 bar_L도 NP에 속하겠죠. 즉 NP=CoNP가 됩니다. 누구 푸실 수 있는분 계시나요?? |