TFNP

計算複雑性理論では、複雑性クラス TFNP は、非決定性多項式時間で解決できる全関数問題のクラスです。つまり、答えがあることが保証され、この答えは多項式時間で確認できる関数問題のクラスです。または、解が存在することが保証されているFNPのサブセットです。略語 TFNP は、「Total Function Nondeterministic Polynomial」の略です。

TFNPには、コンピュータ科学者が関心を持つ多くの自然な問題が含まれています。これらの問題には、整数因数分解、ゲームのナッシュ均衡の発見、局所最適値の探索などがあります。TFNPには計算的に手に負えない問題が含まれていると広く推測されており、そのような問題のいくつかは暗号の仮定の下では困難であることが示されています。^{[1] [2]} ただし、TFNP問題の無条件の手に負えない結果やNP困難性を示す結果は知られていません。TFNPには完全な問題はないと考えられています。^[3]

TFNP クラスは次のように正式に定義されます。

二項関係P ( x , y ) が TFNP に属するのは、xとy の両方が与えられた場合にP ( x , y ) が成り立つかどうかを決定できる決定論的多項式時間アルゴリズムが存在し、すべてのxに対して、最大でxより多項式的に長いyが存在してP ( x , y ) が成り立つ場合のみです。

TFNPは1989年にメギドとパパディミトリウによって初めて定義されましたが^[4]、 TFNPの問題とTFNPのサブクラスは以前に定義され研究されていました^{[5] 。}

• 入力: n + 1 個の項目のセットをn 個の項目 のセットにマッピングする(多項式で計算可能な) マッピングf 。
• 質問: f ( a ) =  f ( b )となる2 つの項目aとb を見つけます。

x をマッピング、y をその定義域内の項目の 2 組とします。問題の 2 項関係P ( x , y ) は、「 xによるyの両方のエントリの像が等しい」という意味を持ち、マッピングは多項式的に計算可能であるため、多項式的に決定可能です。さらに、鳩の巣原理によ​​り、このような組y は任意のマッピングに対して存在する必要があります。

複雑性クラスは2 つの異なる方法で定義できますが、それらの方法は同等であるとはわかっていません。1 つの方法は、のマシン モデルに F を適用します。この定義では、 がTFNP と一致することがわかっています。^[4]これを確認するには、まず、クラスの定義から包含が簡単に従うことに注目してください。TFNP の問題に対するすべての「はい」の回答は、定義により簡単に検証できます。また、TFNP の問題は完全であるため、「いいえ」の回答は存在せず、したがって「いいえ」の回答は簡単に検証できるというのは空虚な真実です。逆の包含については、Rを の 2 項関係とします。R を、 かつ y が「はい」の回答であるとき正確に となるように分解し、 R 2を⁠ ⁠ ⁠で_あり⁠ ⁠ yが「いいえ」の回答であるもの とします。すると、2 項関係はTFNP になります。 ${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}}$${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$${\displaystyle {\mathsf {TFNP}}\subseteq {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$${\displaystyle R_{1}\cup R_{2}}$${\displaystyle (x,0y)\in R_{1}}$${\displaystyle (x,y)\in R}$${\displaystyle (x,1y)}$${\displaystyle (x,y)\in R}$${\displaystyle R_{1}\cup R_{2}}$

もう 1 つの定義では、 が意思決定問題の正常なクラスであることがわかっていることを使用し、 F をそのクラスに適用します。この定義では、の場合、 となります。 ${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}}$${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}={\mathsf {P}}}$${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})={\mathsf {\color {Blue}FP}}}$

NP は、最も広く研究されている複雑性クラスの 1 つです。NP には解決困難な問題があるという推測は広く受け入れられており、最も基本的な困難性の仮定としてよく使用されます。したがって、TFNP が NP とどのように関連しているかを尋ねるのは当然のことです。NP の問題に対する解決策が TFNP の問題に対する解決策を意味することは、簡単にわかります。ただし、NP 困難であることがわかっている TFNPの問題はありません。この事実に対する直感は、TFNP の問題が完全であるという事実から来ています。問題が NP 困難であるためには、何らかのNP 完全問題から対象の問題への還元が存在する必要があります。問題Aから問題Bへの典型的な還元は、 Aの「はい」インスタンスをBの「はい」インスタンスに、 Aの「いいえ」インスタンスをBの「いいえ」インスタンスに送信するマップを作成して分析することによって実行されます。ただし、TFNP の問題は完全であるため、このタイプの還元には「いいえ」インスタンスが存在せず、一般的な手法を適用することが困難になります。この大まかな直感を超えて、TFNP問題のNP困難性を証明することは困難、あるいは不可能であるかもしれないことを示唆する具体的な結果がいくつかあります。たとえば、任意のTFNP問題がNP完全である場合、NP = coNP ^[3]であり、これは一般に誤りであると推測されていますが、複雑性理論では依然として大きな未解決問題です。NPとの関連性がないため、TFNPを独自の独立したクラスとして研究する主な動機となっています。

TFNP の構造は、多くの場合、そのサブクラスの研究を通じて研究されます。これらのサブクラスは、問題の解決を保証する数学定理によって定義されます。TFNP のサブクラスを研究する魅力の 1 つは、TFNP には完全な問題がないと考えられているものの、これらのサブクラスは特定の完全な問題によって定義されるため、推論が容易になることです。

PLS（「多項式局所探索」の略）は、関数の局所最適解を探すプロセスをモデル化するために設計された問題のクラスです。特に、これは次の問題に多項式時間で還元可能な全関数問題のクラスです。

それぞれn入力ビットとn出力ビットを持つ入力回路SとCが与えられた場合、 ⁠ ⁠となるxを見つけます。${\displaystyle C(S(x))\leq C(X)}$

CLS クラスが含まれています。

PPA (「Polynomial time Parity Argument」の略) は、ハンドシェイク補題によって解決が保証される問題のクラスです。つまり、奇数次頂点を持つ無向グラフには必ず別の奇数次頂点が存在するということです。これにはサブクラスPPADが含まれます。

PPP（「多項式時間ピジョンホール原理」の略）は、ピジョンホール原理によって解決が保証される問題のクラスです。より正確には、次のように定義されるピジョン問題に多項式時間で還元できる問題のクラスです。

n入力ビットおよび出力ビットを持つ回路C が与えられた場合、 ⁠ ⁠となるxまたは⁠ ⁠となるx ≠ yを見つけます。${\displaystyle C(x)=0}$${\displaystyle C(x)=C(y)}$

PPPにはPPADクラスとPWPPクラスが含まれる。このクラスの注目すべき問題には短整数解問題が含まれる。^[6]

PPAD (「Polynomial time Parity Argument, Directed」の略) は、ハンドシェイク補題の有向バージョンによって解決が保証される問題に対する PPA の制限です。これは、End-of-a-Line に多項式時間で還元可能な問題の集合として定義されることが多いです。

n入力ビットと出力ビットを持つ回路Sと P が与えられた場合、 ⁠ ⁠または⁠ ⁠ ⁠となるxを見つけます。${\displaystyle S(0)\neq 0}$${\displaystyle P(0)=0}$${\displaystyle P(S(x))\neq x}$${\displaystyle x\neq 0}$${\displaystyle S(P(x))\neq x}$

PPAD は PPA と PPP の交差点にあり、CLS を含みます。

ここで、定義内の回路S は、線の各点を後続の点に送ります。点がシンクの場合は、回路自体に送ります。同様に、線の各点を前の点に送ります。点がソースの場合は、回路自体に送ります。すべての線の外側の点は、PとSの両方で固定されていることによって識別されます(言い換えると、孤立した点はグラフから削除されます)。次に、条件⁠ ⁠ は${\displaystyle P(S(x))\neq x}$、シンクであるか、または他の点yに対してS ( x ) = S ( y ) となる線の終了を定義します。同様に、条件⁠ ⁠ は、線の開始を定義します (0 はソースであると想定しているため、この場合は解がゼロ以外である必要があります)。 ${\displaystyle S(P(x))\neq x}$

連続局所探索 (CLS) は、連続領域上の連続関数の局所最適値を見つけるプロセスをモデル化するために設計された探索問題のクラスです。これは、連続局所点問題に多項式時間で還元可能な問題のクラスとして定義されます。

2 つのリプシッツ連続関数SとCおよびパラメータεとλが与えられた場合、 Cに関するSのε近似不動点、またはCまたはSのλ連続性に違反する 2 つの点を見つけます。

このクラスは、2011年にDaskalakisとPapadimitriouによって初めて定義されました。^[7]これはPPADとPLSの共通部分に含まれており、2020年には証明されました。^{[8] [9]}これは、比較的単純な最適化問題のクラスとして設計されましたが、それでも困難であると考えられている多くの興味深い問題が含まれています。 ${\displaystyle {\mathsf {CLS}}={\mathsf {PPAD}}\cap {\mathsf {PLS}}}$

CLSの完全な問題としては、例えばε- KKT点の探索^[10] 、 ε-バナッハ不動点の探索^[11]、メタメトリック収縮問題^{[12]などがある。}

EOPLとUEOPL（それぞれ「潜在的ラインの終点」と「潜在的ラインの一意の終点」の略）は2020年に導入されました。^[10]

EOPL は、ローカル検索で解決できる検索問題、つまり、多項式時間で 1 つの候補ソリューションから次の候補ソリューションにジャンプできる検索問題を捉えます。EOPL の問題は、各ノードが候補ソリューションであり、エッジに沿って増加するコスト (潜在的とも呼ばれる) を持つ、指数関数的に大きい有向非巡回グラフとして解釈できます。各ノードの入次数と出次数は最大 1 であり、これはノードが指数関数的に長いラインのコレクションを形成することを意味します。各ラインの終端は、そのライン上でコストが最も高いノードです。EOPL には、多項式時間で検索問題 End-of-Potential-Line に簡略化できるすべての問題が含まれています。

入力回路S、P（それぞれn入力ビット、出力ビット）、C（n入力、m出力ビット）、⁠ ⁠ ⁠${\displaystyle S(0)\neq 0}$、⁠ ⁠${\displaystyle P(0)=0}$、⁠ ⁠${\displaystyle C(0)=0}$が与えられたとき 、 xを求める。

• x は行の終わりです⁠ ⁠${\displaystyle P(S(x))\neq x}$、
• xは2行目${\displaystyle S(P(x))\neq x\neq 0}$の始まり、または
• x は増加するコストに違反します⁠ ⁠${\displaystyle P(S(x))=x}$、⁠ ⁠${\displaystyle x\neq S(x)}$および⁠ ⁠${\displaystyle C(S(x))-C(x)\leq 0}$

ここで、S はグラフの各頂点を後続の頂点に送り、頂点がシンクの場合はそれ自身に送ります。同様に、P はグラフの各頂点を先行の頂点に送り、またはそれ自身に送ります。グラフの外側の点は、PとS の両方で固定されていることによって識別されます。すると、最初のソリューション タイプと 2 番目のソリューション タイプは、それぞれ線の上端と下端であり、3 番目のソリューション タイプは、エッジに沿ってポテンシャルが増加するという条件に違反することになります。この最後の条件に違反すると、エンドポイントは線上のポテンシャルを最大化しない可能性があります。したがって、問題は完全です。つまり、ソリューションが見つかるか、条件が満たされていないという短い証明が見つかるかのどちらかです。

UEOPL は、非常によく似た定義ですが、線は 1 本だけであることが約束されています。したがって、上記の 2 番目のタイプのソリューションを見つけることは、最初のタイプのソリューションが一意であることを保証するという約束に違反します。2 番目の線の存在を検出する別の方法を提供するために、4 番目のソリューション タイプが追加されています。

• ⁠ ⁠かつ⁠ ⁠または⁠ ⁠となる2 つの点x、y。${\displaystyle x\neq y,x\neq S(x),y\neq S(y)}$${\displaystyle C(x)=C(y)}$${\displaystyle C(x)<C(y)<C(S(x))}$

このタイプのソリューションは、xとy が異なる線上にあるか、同じ線上の値が厳密に増加するという条件に違反していることを示します。この条件を含める利点は、線の開始点を見つけるよりも、必要に応じてxとy を見つける方が簡単である場合や、コスト増加条件の明示的な違反を見つけるよりも簡単である場合があることです。

UEOPL には、 P 行列-線形相補性問題を解く問題^[10]、立方体における一意のシンクの向きのシンクを探す問題^[10] 、単純な確率ゲームを解く問題^[10]、α-ハムサンドイッチ問題^[13]などが含まれます。UEOPL の完全な問題には、Unique-End-of-Potential-Line、コストがちょうど 1 ずつ増加するその変種、またはP回路のないインスタンス、および One-Permutation-Discrete-Contraction があります。^[10]

EOPL は、UEOPL のような検索問題を、複数行が許可され、行の任意の末尾が検索されるという緩和策で捉えます。現在、EOPL にはあるが UEOPL にはない問題は知られていません。

EOPL は CLS のサブクラスであり、それらが等しいかどうかは不明です。UEOPL は EOPL に自明に含まれています。

FP (複雑度) (「Function Polynomial」の略) は、決定論的多項式時間で解くことができる関数問題のクラスです。 、この包含は厳密であると推測されます。 このクラスは、計算的に扱いやすい (ランダム化なし) と考えられている関数問題のクラスを表します。 TFNP = FP の場合、⁠ ⁠であり、 ⁠ ⁠という事実を考えると直感的にわかるはずです。 ただし、 と推測されることが多いため、 TFNP ≠ FP です。 ${\displaystyle {\mathsf {FP}}\subseteq {\mathsf {CLS}}}$${\displaystyle {\mathsf {P}}={\mathsf {NP}}\cap {\mathsf {coNP}}}$${\displaystyle {\mathsf {TFNP}}={\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}\cap {\mathsf {coNP}}}$