| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2003년 12월 30일 화요일 오후 01시 08분 34초 제 목(Title): Re: CMI문제 P vs NP > 물론 factoring이 NP-Complete이 아니라는건 뭐 잘 아실테고. NP != P 인 게 증명되지 않는 이상 이런 말은 성립하지 않습니다. :) FACT: 1. NP=P 라면, sorting도 NP-complete가 됩니다. 2. factor는 P 에 속하는지, NP-complete인지, co-NP-complete인지 알려져 있지 않은 문제입니다. quantum computer에서 P 시간에 풀린다는 사실 말고는.. 어쨌든 NP != P 라면 factoring은 이 세 class 모두에 속하지 않을 거라는 게 많은 사람들의 믿음입니다. http://en.wikipedia.org/wiki/Integer_factorization -- 박.. |