NP (복잡도)

NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이다.

NP에 속하는 문제는 결정론적 튜링 기계로 다항 시간에 검증이 가능하고, 그 역도 성립한다. 또한 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 문제는 비결정론적 튜링 기계로도 다항 시간 안에 풀 수 있으므로, P 집합은 NP 집합의 부분집합이다. 이때 P가 NP의 진부분집합인지, 혹은 P와 NP가 같은지에 대해서는 아직 알려지지 않았고, 이 문제는 P-NP 문제로 불린다.

NP=PCP(log n, O(1))^[1]

예시

자연수의 소인수분해에 대한 결정문제는 NP에 속한다. 가령, 100자리 숫자에 대한 소인수분해는 매우 오래 걸릴 수 있지만, 그 소인수분해의 결과를 알고 있다면 해당 숫자를 단순히 곱하는 것으로도 소인수분해가 잘 이루어졌는지 확인할 수 있기 때문에 다항 시간 안에 검증이 가능하다.

같이 보기

• NP-난해
• NP-완전

각주

1. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. “Proof verification and hardness of approximation problems”. Journal of the ACM 45(3):501-555, 1998. ECCC TR98-008. CS1 관리 - 여러 이름 (링크)