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

같이 보기

편집

각주

편집
  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.