NP (복잡도)

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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

참고[편집]