NP (복잡도)
위키백과 ― 우리 모두의 백과사전.
계산 복잡도 이론에서, NP는 비결정론적 튜링 기계로 다항시간에 풀 수 있는 판정문제의 집합이다. 다시 말해, NP는 결정론적 튜링 기계로 다항시간에 '검증'(verify)할 수 있는 문제들의 집합이다. NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이다.
| 주요 복잡도 종류 (더 보기) |
|---|
|
P | NP | Co-NP | NP-C | Co-NP-C | NP-난해 | UP | #P | #P-C | L | NL | NC | P-C | PSPACE | PSPACE-C |
