UP(복잡성)

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "UP" 복잡성 – 뉴스 · 신문 · 책 · 학자 · JSTOR(2018년 8월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

복잡성 이론에서 UP(확실하지 않은 비결정론적 다항식 시간)는 각 입력에 대해 최대 하나의 허용 경로를 갖는 모호하지 않은 튜링 기계의 다항 시간 내에 해결할 수 있는 의사결정 문제의 복잡도 등급이다.UP는 P를 포함하고 NP에 포함되어 있다.

NP의 공통적인 개혁은 주어진 대답이 다항식 시간에 결정론적 기계에 의해 검증될 수 있는 경우에만 언어가 NP에 있다고 명시한다.마찬가지로, 주어진 대답이 다항식 시간에 검증될 수 있다면 언어는 UP이며, 검증기는 각 문제 인스턴스에 대해 최대 한 개의 대답만 허용한다.보다 형식적으로 L은 2입력 다항식 시간 알고리즘 A와 다음과 같은 상수 c가 있으면 UP에 속한다.

l에 x가 있으면 $y{\displaystyle }$= ${\displaystyle O}$( x ${\displaystyle c}$${\displaystyle {}^{}}$) ${\displaystyle$ y = O( ${\displaystyle x}$$^c})$ = ${\displaystyle 1}$ ${\displaystyle A$}을$($를) 가진 고유한 인증서 y가 존재한다.

x가 L에 없으면 y${\displaystyle }$= ${\displaystyle O(}$ ${\displaystyle {}^{}}$ ${\displaystyle c}$${\displaystyle {}^{}}$) ${\displaystyle y$= $O($ ${\displaystyle x}$$^c})$ = ${\displaystyle 1}$ ${\displaystyle A$}을$($를) 가진 인증서 y가 없다.

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

UP(및 그것의 보완적 co-UP)는 정수 인자화 문제와 패리티 게임 문제를 모두 포함하고 있다. 이러한 문제에 대한 단호한 노력이 아직 어떤 다항 시간 해결책을 찾지 못했기 때문에 P=UP 또는 P=(UP co co-UP)를 보여주기가 어려울 것으로 의심된다.

발리안트-바지라니 정리는 NP가 RP에^Promise-UP 포함되어 있다고 기술하고 있는데, 이는 NP의 어떤 문제에서 Promise-UP의 문제로 무작위적인 축소가 있음을 의미한다.

UP는 완전한 문제가 있는 것으로 알려져 있지 않다.^[1]

참조

참조

• 레인 A. Hemaspaandra 및 Jorg Rothe, Unambiguous Computing: 부울 계층 구조 및 희소 튜링-완전 세트, SIAM J. Compute, 26(3)(1997년 6월), 634–653