# 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을 다항 시간에 검증한다.

원본 주소 ‘http://ko.wikipedia.org../../../u/p/_/UP_%28%EB%B3%B5%EC%9E%A1%EB%8F%84%29_6e57.html’

분류: 복잡도 종류

##### Views

- 문서
- 토론
- 현재 버전

##### 찾기

##### 다른 언어

- English
- Español
- 日本語