UP (복잡도) 문서 원본 보기

{{위키데이터 속성 추적}}
[[계산 복잡도 이론]]에서 '''UP''' 곧, '''모호하지 않은 비결정론적 다항 시간'''({{lang|en|'''U'''nambiguous non-deterministic '''P'''olynomial-time}})이란 [[비결정론적 튜링 기계]]가 입력마다 받아들이는 경로를 최대 한 개만으로 해서 [[다항 시간]]에 풀 수 있는 [[판정 문제]]들의 [[복잡도 종류]]이다. '''UP'''는 '''[[P (복잡도)|P]]'''를 포함하고, '''[[NP (복잡도)|NP]]'''에 속한다. '''P''' &ne; '''UP'''이거나 '''UP''' &ne; '''NP'''일 (아니면, 둘 다일) 것으로 추측하고 있다. 그렇지 않으면 '''P''' = '''NP'''이기 때문이다. (학계에서는 P &ne; NP일 것으로 보고 있다.) 두 가지 추측이 모두 참일 가능성이 높다.

흔히 '''NP'''를 이렇게 다시 형식화한다: 어떤 언어가 '''NP'''라는 것과 답이 주어질 때 결정론적 기계로 다항시간에 검증할 수 있다는 것은 동치이다. 비슷하게, 주어진 답이 다항 시간에 검증될 수 있고, 검증 기계가 문제 인스턴스마다 답변을 최대 ''한 개''만 받아들이면, 그 언어는 '''UP'''이다. 더 형식적으로 쓰면, 언어 <math>L</math>은 입력을 두 개 받는 다항 시간 알고리즘 ''A''와 다음 조건을 만족하는 상수 c가 존재할 때 '''UP'''가 된다.
:<math>L = \{x \in \{0,1\}^* | \exists! \mbox{ certificate, } y \mbox{ with } |y| = O(|x|^c) \mbox{ such that } A(x,y) = 1\}</math>
알고리즘 <math>A</math>는 <math>L</math>을 다항 시간에 검증한다.

{{복잡도 종류}}

[[분류:복잡도 종류]]