이것은 문서의 이전 버전입니다!


NP-완전

NP-complete. NP-C라고도 씀.

NP에 속하면서 다른 모든 NP 문제보다 적어도 쉽지 않은 문제들이 속한다. NP에 속하지는 않고 후자임이 알려진 문제는 NP-난해라고 함.

NP-완전한 문제는 P = NP가 증명되지 않는 한 다항 시간 안에 풀 수 없지만 그렇다고 항상 지수 시간이 걸리는 건 아니다. 지수 시간이 걸리는 문제의 집합은 EXPTIME이며 NP = EXPTIME인지는 미해결 문제임. 즉 재수 없으면 다항과 지수 사이에 있는 것들이 걸릴 수도 있…


도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-05-30 18:25 | 외부 편집기