UP (복잡도)
위키백과 ― 우리 모두의 백과사전.
계산 복잡도 이론에서 UP 곧, 모호하지 않은 비결정론적 다항 시간(Unambiguous non-deterministic Polynomial-time)이란 비결정론적 튜링 기계가 입력마다 받아들이는 경로를 최대 한 개만으로 해서 다항 시간에 풀 수 있는 판정 문제들의 복잡도 종류이다. UP는 P를 포함하고, NP에 속한다. P ≠ UP이거나 UP ≠ NP일 (아니면, 둘 다일) 것으로 추측하고 있다. 그렇지 않으면 P = NP이기 때문이다. (학계에서는 P ≠ NP일 것으로 보고 있다.) 두 가지 추측이 모두 참일 가능성이 높다.
흔히 NP를 이렇게 다시 형식화한다: 어떤 언어가 NP라는 것과 답이 주어질 때 결정론적 기계로 다항시간에 검증할 수 있다는 것은 동치이다. 비슷하게, 주어진 답이 다항 시간에 검증될 수 있고, 검증 기계가 문제 인스턴스마다 답변을 최대 한 개만 받아들이면, 그 언어는 UP이다. 더 형식적으로 쓰면, 언어 L은 입력을 두 개 받는 다항 시간 알고리즘 A와 다음 조건을 만족하는 상수 c가 존재할 때 UP가 된다.
- L = {x in {0,1}* | ∃! certificate, y with |y| = O(|x|c) such that A(x,y) = 1}
알고리즘 A는 L을 다항 시간에 검증한다.
| 주요 복잡도 종류 (더 보기) |
|---|
|
P | NP | co-NP | NP-C | co-NP-C | NP-난해 | UP | #P | #P-C | L | NL | NC | P-C | PSPACE | PSPACE-C |
