약속문제

계산 복잡성 이론에서 약속 문제는 입력이 가능한 모든 입력의 특정 부분집합에 속하도록 약속된 의사결정 문제의 일반화다.^[1]의사결정 문제와 달리, 예 인스턴스(알고리즘이 예스를 반환해야 하는 입력)와 어떤 인스턴스도 모든 입력 집합의 집합이 소모되지 않는다.직관적으로, 알고리즘은 입력이 실제로 예(Yes) 인스턴스 집합에 속하거나 예(Yes) 인스턴스가 없음을 약속받았다.예스도 아니요도 아닌 입력 내용이 있을 수 있다.약속 문제 해결을 위한 알고리즘에 그러한 입력이 주어지면, 알고리즘은 어떤 것이든 출력할 수 있고 심지어 정지하지 않을 수도 있다.

형식 정의

A decision problem can be associated with a language ${\displaystyle L\subseteq \{0,1\}^{*}}$, where the problem is to accept all inputs in ${\displaystyle L}$ and reject all inputs not in ${\displaystyle L}$. For a promise problem, there are two languages, ${\displaystyle L_{\text{$$YES}}$ 및 L$$ ${\displaystyle {\text{NO}}_{}}$ ${\$$NO$ 즉 $L{\displaystyle {}_{}}$ ${\displaystyle {\text{YES}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\text{NO}}_{}}$= ${\displaystyle \varnothing }$ ${\displaystyle L_{\text}$을(를) 의미하는 분리되어야 함$YES}}\cap L_{\text{$$NO}}=\varnothing$ $\},$ $L{\displaystyle {}_{}}$ ${\displaystyle {\text{YES}}_{}}$ ${\$의 모든 입력이 해당됨.$YES}}$을(를) 승인하고$$ L ${\displaystyle {\text{NO}}_{}}$ ${\$$NO}}}$은(는) 거부된다$$.$L{\displaystyle {}_{}}$ ${\displaystyle {\text{YES}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\text{NO}}_{}}$ ${\$$YES}}\컵 L_{\text{$$NO}}}$을(를) 약속이라고 한다$$.입력이 약속에 속하지 않으면 출력에 대한 요구사항이 없다.만약 그 약속이${\displaystyle }${${\displaystyle 0}$, ${\displaystyle 1{}^{\ast }}$ ∗ ${\$\{$0,1$과 같다면 이 역시 결정문제로, 그 약속은 사소한 것이라고 한다.

예

많은 자연적인 문제들은 실제로 약속된 문제들이다.예를 들어 다음 문제를 고려하십시오.지시된 Acyclic 그래프를 사용하여 그래프에 길이 10의 경로가 있는지 확인하십시오.예(Yes) 인스턴스는 길이 10의 경로를 가진 순환 그래프인 반면, 어떤 인스턴스도 길이 10의 경로가 없는 순환 그래프인 경우 방향 지정되지 않는다.그 약속은 지시된 반복 그래프들의 집합이다.이 예에서 약속은 쉽게 확인할 수 있다.특히 주어진 그래프가 주기적인지 확인하는 것은 매우 쉽다.그러나 약속된 재산은 평가하기 어려울 수 있다.예를 들어, "해밀턴 그래프에 4의 사이클이 있는지 판단하라."라는 문제를 고려해 보십시오. 현재 약속은 평가하기 어려운 NP이지만, 4의 사이클은 다항식 시간에 확인할 수 있기 때문에 약속 문제는 쉽게 해결할 수 있다.

참고 항목

• 계산 문제
• 의사결정 문제
• 최적화 문제
• 검색문제
• 카운팅 문제(복잡성)
• 함수 문제
• TFNP

참조

설문 조사

• Goldreich, Oded (2006). "On Promise Problems (a survey)". Theoretical Computer Science: Essays in memory of Shimon Even. LNCS. Vol. 3895. pp. 254–290. doi:10.1007/11685654_12.
• Sahai, A.; Vadhan, S.P. (1997). "A complete promise problem for statistical zero-knowledge". FOCS 1997. pp. 448–457. CiteSeerX 10.1.1.34.6920. doi:10.1109/SFCS.1997.646133.
• Even, Shimon; Selman, Alan L.; Yacobi, Yacov (1984). "The complexity of promise problems with applications to public-key cryptography". Information and Control. 61 (2): 159–173. doi:10.1016/S0019-9958(84)80056-X.