====== NP-완전 ======

[[en>NP-complete]]. NP-C라고도 씀.

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

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

{{tag>전산학}}