NP (복잡도)
위키백과 ― 우리 모두의 백과사전.
NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이다.
NP에 속하는 문제는 결정론적 튜링 기계로 다항 시간에 검증이 가능하고, 그 역도 성립한다. 또한 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 문제는 비결정론적 튜링 기계로도 다항 시간 안에 풀 수 있으므로, P 집합은 NP 집합의 부분집합이다. 이때 P가 NP의 진부분집합인지, 혹은 P와 NP가 같은지에 대해서는 아직 알려지지 않았고, 이 문제는 P-NP 문제로 불린다.
|
|
|---|
| P · NP · co-NP · NP-C · co-NP-C · NP-난해 · UP · #P · #P-C · L · NL · NC · P-C · PSPACE · PSPACE-C · EXPTIME · EXPSPACE · PR · RE · co-RE · RE-C · co-RE-C · R · BQP · BPP · RP · ZPP · PCP · IP · PH |
