UP (복잡도)

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

계산 복잡도 이론에서 UP 곧, 모호하지 않은 비결정론적 다항 시간(Unambiguous non-deterministic Polynomial-time)이란 비결정론적 튜링 기계가 입력마다 받아들이는 경로를 최대 한 개만으로 해서 다항 시간에 풀 수 있는 판정 문제들의 복잡도 종류이다. UPP를 포함하고, NP에 속한다. PUP이거나 UPNP일 (아니면, 둘 다일) 것으로 추측하고 있다. 그렇지 않으면 P = NP이기 때문이다. (학계에서는 P ≠ NP일 것으로 보고 있다.) 두 가지 추측이 모두 참일 가능성이 높다.

흔히 NP를 이렇게 다시 형식화한다: 어떤 언어가 NP라는 것과 답이 주어질 때 결정론적 기계로 다항시간에 검증할 수 있다는 것은 동치이다. 비슷하게, 주어진 답이 다항 시간에 검증될 수 있고, 검증 기계가 문제 인스턴스마다 답변을 최대 한 개만 받아들이면, 그 언어는 UP이다. 더 형식적으로 쓰면, 언어 L은 입력을 두 개 받는 다항 시간 알고리즘 A와 다음 조건을 만족하는 상수 c가 존재할 때 UP가 된다.

L = \{x \in \{0,1\}^* | \exist! \mbox{ certificate, } y \mbox{ with } |y| = O(|x|^c) \mbox{ such that } A(x,y) = 1\}

알고리즘 AL을 다항 시간에 검증한다.