TFNP

계산 복잡성 이론에서 복잡성 등급 TFNP는 비결정론적 다항식 시간에 해결할 수 있는 총함수 문제의 등급이다.즉, 해답이 보장되는 것이 기능 문제의 등급이며, 이 해답은 다항 시간 내에 확인할 수 있거나, 동등하게 솔루션이 존재한다고 보장되는 FNP의 서브셋이다.약칭 TFNP는 "Total Function Noneterministic Polyomial"을 의미한다.

TFNP는 컴퓨터 과학자들에게 관심있는 많은 자연적인 문제들을 포함하고 있다.이러한 문제들에는 정수 인자화, 게임의 내시 균형 찾기, 지역적 최적성 검색 등이 포함된다.TFNP는 계산적으로 난해한 문제를 포함한다고 널리 추측되고 있으며, 그러한 문제들은 암호화된 가정 하에서 어려운 것으로 밝혀졌다.^[1][2]그러나 TFNP 문제의 NP-강성을 보여주는 알려진 무조건적인 난치성 결과나 결과는 없다.TFNP는 완전한 문제를 가지고 있지 않다고 여겨진다.^[3]

형식 정의

클래스 TFNP는 다음과 같이 공식적으로 정의된다.

2진수 관계 P(x,y)는 P(x,y)가 x와 y를 모두 보유하는지 여부를 결정할 수 있는 결정론적 다항 시간 알고리즘이 있는 경우에만 TFNP에 있으며, 모든 x에 대해 P(x,y)가 보유하는 x보다 다항수적으로 긴 y가 존재한다.

앞서 TFNP 문제와 TFNP의 하위 분류가 정의되고 연구되었음에도 불구하고 1989년 메기도와 파파디미트리오에 의해 처음 정의되었다.^[4][5]

기타 복잡성 클래스에 연결

F(NP ∩ coNP)

복잡도 등급 $F{\displaystyle \mathsf{}(N\mathsf{}}$ ${\displaystyle \mathsf{P}}$ ${\displaystyle \cap }$ ${\displaystyle c\mathsf{}}$ ${\displaystyle \mathsf{o}}$ ${\displaystyle \mathsf{N}}$ $){\displaystyle {\mathsf{F}}({\mathsf{NP}}\cap{\mathsf {coNP})$는 두 가지 다른 방법으로 정의할 수 있으며$$, 그러한 방법은 동등하다고 알려져 있지 않다.One way applies F to the machine model for ${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}}$. It is known that with this definition, ${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$ coincides with TFNP.^[4]To see this, first notice that the inclusion ${\displaystyle {\mathsf {TFNP}}\subseteq {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$ follows easily from the definitions of the classes.TFNP의 문제에 대한 모든 '예' 답변은 정의로 쉽게 검증할 수 있으며, TFNP의 문제는 총체적이기 때문에 '아니오' 답변이 없기 때문에 '아니오' 답변이 쉽게 검증될 수 있다는 것은 공허한 사실이다.For the reverse inclusion, let R be a binary relation in ${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$. Decompose R into ${\displaystyle R_{1}\cup R_{2}}$ such that ${\displaystyle (x,0y)\in R_{1}}$ precisely when ${\$$displaystyle (x,y)\in R}$과 y는 "yes" 대답이고, r은₂ $({\displaystyle x,}$ ${\displaystyle 1}$ ${\displaystyle y}$)$$${\displaystyle (x,1y)}$과 같은 (${\displaystyle x}$ ,${\displaystyle y}$)이 되도록 하고, y는 "no" 대답이다.그러면 이진관계 $R{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {R\mathrm{}}_{}}$ 2 ${\$2}}$개가$ TFNP에 있다$$.

다른 ${\displaystyle \mathsf{정의}}$에서는 N $P{\displaystyle \mathsf{}}$ ${\displaystyle \cap }$ ${\displaystyle c\mathsf{}}$ ${\displaystyle \mathsf{o}}$ N ${\displaystyle \mathsf{P}}$ ${\$이(가) 올바른 수준의 의사결정 문제로 알려져 있으며$$, F를 해당 등급에 적용한다.With this definition, if ${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}={\mathsf {P}}}$ then ${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})={\mathsf {\color {Blue}$$FP$

NP 연결

NP는 가장 널리 연구되고 있는 복잡성 수업 중 하나이다.NP에 난해한 문제가 있다는 추측은 널리 받아들여져 가장 기본적인 경도 가정으로 자주 사용된다.따라서 TFNP가 NP와 어떤 관련이 있는지 묻는 것은 당연하다.NP의 문제 해결이 TFNP의 문제에 대한 해결책을 내포할 수 있다고 보는 것은 어렵지 않다. 다만, NP-hard라고 알려진 TFNP 문제는 없다.이 사실에 대한 직관은 TFNP의 문제들이 총체적이라는 사실에서 나온다.문제가 NP-hard가 되려면 NP-완전 문제에서 관심 문제로의 감소가 존재해야 한다.문제 A에서 문제 B로 "예" 인스턴스(instance)를 B의 "예" 인스턴스(instance)" 인스턴스(instance)로, A의 "아니오" 인스턴스(instance)"를 B의 "아니오" 인스턴스(instance)"로 전송하는 맵을 만들어 분석함으로써 일반적인 A 문제 B로 축소 작업을 수행한다.그러나 TFNP 문제는 총체적이기 때문에 이러한 유형의 감축에 대한 "없음" 사례가 없어 공통 기법을 적용하기 어렵다.이러한 거친 직관을 넘어, TFNP 문제에 대한 NP 경직성을 입증하는 것이 어렵거나 심지어 불가능할 수도 있다는 것을 암시하는 몇 가지 구체적인 결과가 있다.예를 들어, 어떤 TFNP 문제가 NP-완전이라면,^[3] NP = coNP는 일반적으로 거짓으로 추측되지만, 여전히 복잡성 이론에서 주요한 개방적인 문제다.이러한 NP와의 연계 부족은 TFNP가 독자적인 계층으로서 연구하게 된 주요한 동기부여가 된다.

주목할 만한 하위 클래스

TFNP의 구조는 그 하위 분류 연구를 통해 연구되는 경우가 많다.이 하위 분류들은 문제에 대한 해법이 보장되는 수학적인 정리에 의해 정의된다.TFNP의 하위 클래스를 연구하는 한 가지 호소력은 TFNP가 완전한 문제를 가지고 있지 않다고 생각되지만, 이러한 하위 클래스는 특정 전체 문제로 정의되어 있어 추론하기 쉽다는 것이다.

제발

PLS(Polynomial Local Search(폴리노멀 로컬 검색)의 약자)는 함수에 대한 로컬 최적 검색 프로세스를 모델링하기 위해 고안된 문제의 한 종류다.특히 다항식 시간을 다음 문제로 환원할 수 있는 것은 총함수 문제의 등급이다.

입력 및 출력 비트가 각각 n개인 입력 회로 ${\displaystyle S}$와 ${\displaystyle C}$가 주어진 경우 C(${\displaystyle }S{\displaystyle }$ ( )${\displaystyle \le }$ C (${\displaystyle X}$ )${\displaystyle$C(S$)(x)\leq C(X)}$과 같은 x를 찾으십시오$.$

클래스 CLS가 들어 있다.

PPA

PPA("폴리놈 시간 패리티 인수"의 약자)는 핸드셰이킹 보조정리기로 해결책이 보장되는 문제의 등급이다. 즉, 도수가 홀수인 비방향 그래프는 또 다른 오도 정점을 가져야 한다.그것은 하위 클래스 PWPP와 PPAD를 포함하고 있다.

PPP

PPP(Polyomnormal time Peponyhole 원칙의 약자)는 Peponyhole 원칙에 의해 해결책이 보장되는 문제의 등급이다.보다 정확히 말하면, 다항식 시간에 비둘기 문제에 축소될 수 있는 문제의 등급으로, 다음과 같이 정의된다.

입력 및 출력 비트가 n개인 회로 C는 $C{\displaystyle (}$ ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle C(x)=0}$ 또는$$ $C{\displaystyle (}$ ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle C(}$ y${\displaystyle }$) ${\displaystyle C(x)=C(y)}$인 x를 찾으십시오$.$

PPP에는 PPAD와 PWPP 클래스가 포함되어 있다.이 세분류에서 주목할 만한 문제에는 짧은 정수해법 문제가 있다.^[6]

PPAD

PPAD("폴리놈 시간 패리티 인수, 지시됨"을 의미함)는 핸드셰이크 보조정리 버전의 지시된 버전에 의해 해결책이 보장되는 문제에 대한 PPA의 제한이다.다항식 시간을 줄여서 종단선(End-of-a-Line)으로 줄일 수 있는 문제의 집합으로 정의되는 경우가 많다.

Given circuits S and P with n input and output bits ${\displaystyle S(0)\neq 0}$ and ${\displaystyle P(0)=0}$, find x such that ${\displaystyle P(S(x))\neq x}$ or ${\displaystyle x\neq 0}$ such that ${\displaystyle S(P(x))\neq x}$.

PPAD는 PPA와 PPP의 교차점에 있으며, CLS가 포함되어 있다.

여기서 정의에 있는 회로 S는 선의 각 점을 후임자에게, 또는 그 점이 싱크대일 경우 그 자신에게 보낸다.마찬가지로 P는 선의 각 점을 전임자에게, 또는 그 점이 출처인 경우 자신에게 보낸다.모든 선 외부의 점들은 P와 S 둘 다에 고정됨으로써 식별된다(즉, 그래프에서 모든 분리된 점이 제거됨).Then the condition ${\displaystyle P(S(x))\neq x}$ defines the end of a line, which is either a sink or is such that S(x) = S(y) for some other point y; similarly the condition ${\displaystyle S(P(x))\neq x}$ defines the beginning of a line (since we assume that 0 is a source, we require the solution이 경우에는 0이 아니다).

CLS

CLS(Continuous Local Search, "Continuous Local Search"의 줄임말)는 연속 도메인 상에서 연속함수의 로컬 최적점을 찾는 과정을 모형화하기 위해 고안된 검색 문제의 한 종류다.이는 연속 로컬포인트 문제로 축소할 수 있는 다항식 시간으로 정의된다.

Lipschitz의 연속함수 S와 C, 매개변수 ε과 λ을 두 개 주어진 경우, C 또는 S의 λ-연속성을 위반하는 두 점 또는 C에 관하여 ε 근사치 고정점 S를 찾는다.

이 수업은 2011년 Daskalakis와 Papadimitriou에 의해 처음 정의되었다.^[7]그것은 PPAD고 PLS의 교차점에 2020년에 CLS)PPAD∩ PLS{\displaystyle{\mathsf{CommonLanguageSpecification}}={\mathsf{PPAD}}\cap{\mathsf{PLS}가 입증된 포함되어 있}}.[8][9]이었다 설계된 클래스의 비교적 단순한 최적화 문제는 아직도 포함하는 많은 흥미로운 문제 있기는 b.ehard

예를 들어 CLS의 전체 문제는 ε-KKT 지점 찾기,^[10] ε-Banach 고정 지점^[11] 찾기, 메타-메트릭-콘트랙션 문제 등이다.^[12]

EOPLE 및 UEOPLE

EOPLE과 UEOPLE ("전위 라인의 끝"과 "전위 라인의 독특한 끝"을 의미함)은 2020년까지 도입되었다.^[10]

EOPLE은 현지 검색으로 해결할 수 있는 검색 문제를 캡처한다. 즉, 다항식 시간 내에 한 후보 솔루션에서 다음 후보 솔루션으로 도약할 수 있다.EOPLE의 문제는 각 노드가 후보 솔루션이고 가장자리를 따라 증가하는 비용(전위성이라고도 함)이 있는 기하급수적으로 큰 방향의 반복 그래프로 해석될 수 있다.각 노드의 내도와 외도는 최대 하나이며, 이는 노드가 기하급수적으로 긴 행의 집합을 형성한다는 것을 의미한다.각 라인의 끝은 해당 라인에서 비용이 가장 높은 노드다.EOPL에는 다항식 시간 내에 검색 문제 End-of-Potential-Line으로 줄일 수 있는 모든 문제가 포함되어 있다.

입력 및 출력 비트가 각각 n개인 입력 회로 S, P, 그리고 n 입력 및 m 출력 비트가 있는 $C{\displaystyle }$, S${\displaystyle }$( ${\displaystyle 0}$) ${\displaystyle \ne }$ ${\displaystyle 0}$ ${\displaystyle$ S$(0)\neq$0$\},$${\displaystyle }P{\displaystyle }$ (${\displaystyle 0}$) = ${\displaystyle 0}${\$displaystyle P$(0$)=$$0{\displaystyle }$$\},$${\displaystyle }$C (${\displaystyle 0}$) = ${\displaystyle 0}${\$displaystystyle C$(0$)=0$ 그러한 x를 찾는다.

• x는 선 $P{\displaystyle }$( S${\displaystyle }$( ${\displaystyle x}$)의 끝이다.$$${\displaystyle \ne }$ ${\displaystyle x}$ ${\displaystyle P(S(x)\neq$ x$},$
• x는 두 번째 줄 $S{\displaystyle }$( ${\displaystyle P}$( ${\displaystyle x}$)${\displaystyle }$the ${\displaystyle x\ne }$ ${\displaystyle 0}$(\$displaystyle S(P(x))\neq x\neq$ 0$}$또는
• x는 ${\displaystyle \mathrm{증가}}$하는 비용 $P{\displaystyle }$(${\displaystyle S}$( (${\displaystyle x}$) = x$${\$displaystyle P(S)(x)=x$ $x{\displaystyle s}$ S${\displaystyle }$(${\displaystyle x}$ )$${\$displaystyle$x\$neq$S$(x$$)}$ $및$ C (${\displaystyle }$S (${\displaystyle x}$)${\displaystyle 0}$ 0 ($x$) ${\displaystystyle$ C$(x$)\$leq$ 0}을 위반한다$.$

여기서 S는 그래프의 각 꼭지점을 후임자에게, 또는 꼭지점이 싱크대일 경우 자신에게 보낸다.마찬가지로 P는 그래프의 각 꼭지점을 이전 정점 또는 그 자신에게 보낸다.그래프 밖의 점은 P와 S 둘 다에 고정하여 식별한다.그러면 제1의 용액형과 제2의 용액형은 각각 선의 상단과 하단의 용액형이 되고, 제3의 용액형은 가장자리를 따라 전위가 증가하는 조건의 위반이다.이 마지막 조건을 위반하면 엔드포인트가 라인에서 잠재력을 최대화하지 못할 수 있다.따라서 문제는 다음과 같다.해결책이 발견되거나 조건이 충족되지 않는다는 짧은 증거가 발견된다.

UEOPLE은 매우 유사하게 정의되지만, 단 하나의 선만이 있을 것으로 약속된다.따라서 위의 두 번째 유형의 솔루션을 찾는 것은 첫 번째 유형의 솔루션이 고유하다는 약속을 위반할 수 있다.네 번째 솔루션 유형이 추가되어 두 번째 라인의 존재를 감지할 수 있는 또 다른 방법을 제공한다.

• two points x, y such that ${\displaystyle x\neq y,x\neq S(x),y\neq S(y)}$ and either ${\displaystyle C(x)=C(y)}$ or ${\displaystyle C(x)<C(y)<C(S(x))}$.

이러한 유형의 용액은 x와 y가 서로 다른 선에 있음을 나타내거나, 같은 선의 값이 엄격히 증가하고 있다는 조건의 위반을 나타낸다.이 조건을 포함하면 라인의 시작을 찾는 것보다 필요에 따라 x와 y를 찾는 것이 더 쉬울 수 있거나 증가하는 비용 조건을 명시적으로 위반할 수 있다는 장점이 있다.

UEOPLE은 무엇보다도 P-매트릭스-선형 보완성 문제를 해결하고, ^[10]큐브에서 유니크 싱크 방향의 싱크대를 찾아 간단한 확률 ^[10]게임과^[10] α-Ham 샌드위치 문제를 해결하는 문제를 담고 있다.^[13]UEOPLE의 완전한 문제점은 Unique-End-of-Potential-Line이며, 일부 변형에서는 비용이 정확히 1 증가하거나 P 회로가 없는 인스턴스(instance) 및 One-Permutation-Discrete-Contraction이다.^[10]

EOPLE은 UEOPLE의 그것과 같은 검색 문제를 여러 줄이 허용되고 선의 끝에서 검색된다는 여유를 가지고 포착한다.현재 EOPLE에는 있지만 UEOPLE에는 없는 것으로 알려진 문제가 없다.

EOPL은 CLS의 하위 등급으로, 동일 여부를 알 수 없다.UEOPLE은 EOPLE에 소상히 포함되어 있다.

FP

FP(복잡성) ("기능 다항식"을 의미)는 결정론적 다항식 시간에 해결할 수 있는 기능 문제의 등급이다.${\displaystyle \mathsf{F}}$ ${\displaystyle \mathsf{P}}$ ${\displaystyle \subseteq }$ ${\displaystyle C\mathsf{}}$ ${\displaystyle \mathsf{L}}$ S ${\$ 이 포함이 엄격한 것으로 추측된다.이 세분류는 (임의화 없이) 계산적으로 처리할 수 있다고 여겨지는 기능 문제의 등급을 나타낸다.If TFNP = FP, then ${\displaystyle {\mathsf {P}}={\mathsf {NP}}\cap {\mathsf {coNP}}}$, which should be intuitive given the fact that ${\displaystyle {\mathsf {TFNP}}={\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$. However, it is generally conjectured tha$T{\displaystyle \mathsf{}}$ ${\displaystyle \ne }$ N ${\displaystyle \mathsf{P}}$ ${\displaystyle \cap }$ C ${\displaystyle \mathsf{o}}$ ${\displaystyle \mathsf{N}}$ P ${\$ 그래서 TFNP ≠ FP$.$

참조