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\}^{*}|\exists !{\mbox{ certificate, }}y{\mbox{ with }}|y|=O(|x|^{c}){\mbox{ such that }}A(x,y)=1\}$

알고리즘 $A$는 $L$을 다항 시간에 검증한다.