NP 복잡도

Nondeterministic, Polynomial time. 비결정적튜링기계(NTM)에서 다항시간 안에 풀 수 있는 결정문제의 집합. 함수문제에 대응되는 복잡도는 FNP이다. 가끔씩 NP를 Non-polynomial time으로 착각하는 사람이 있지만 지수시간 안에 풀 수 있는 문제들의 집합은 EXPTIME으로 따로 복잡도가 있다.

비결정적 튜링 기계는 좀 복잡하므로 보통의 결정적 튜링 기계(DTM)를 사용하여 NP를 다시 정의하면, NP는 문제를 풀고 나서 그 문제의 입력, 출력 및 출력이 맞는지 검증하는 데 도와줄 힌트(certificate)를 주면 그 힌트를 사용해서 입출력이 올바른지 다항 시간 안에 검사(verify)할 수 있는 모든 문제의 집합이다. 이 때 힌트로 주는 데이터 역시 그 크기가 입력 길이에 대한 다항식으로 주어져야 한다. 이 정의가 NTM을 사용한 것과 같은 이유는, 이 정의를 그대로 사용하면 NTM이 비결정적으로 힌트를 만들어 낸 뒤에 검사를 해서 맞는 것만 통과시키면¹⁾ 다항 시간만이 걸리기 때문이다.

P와 NP는 전산학에서 가장 중요한 복잡도 종류들이다. 둘 사이의 관계는 P = NP 문제로 잘 알려진 미해결 문제이고, 또한 전산학에서 많은 문제들이 NP와 깊게 관련된 NP-완전 또는 NP-난해 복잡도에 속하는 것으로 알려져 있다.