Loading article…
計算複雑性理論において、PPA は複雑性クラスであり、「（グラフ上の）多項式パリティ論証」を表します。1994年にChristos Papadimitriou [1] (528 ページ) によって導入された PPA は、 TFNPのサブクラスです。これは、ハンドシェイク補題を適用することで完全であることが示される探索問題のクラスです。つまり、次数が奇数の頂点を持つ無向グラフには、次数が奇数の別の頂点が必ず存在します。この観察は、グラフと奇数次数の頂点が与えられ、別の奇数次数の頂点を見つけるように求められた場合、存在が保証されているものを探していることを意味します (したがって、完全探索問題があります)。
意味
PPA は次のように定義されます。頂点が - ビットのバイナリ文字列であるグラフがあり、グラフが頂点を入力としてその近傍を出力する多項式サイズの回路によって表されるとします。(これにより、局所探索を効率的に実行できる指数関数的に大きなグラフを表現できることに注意してください。) さらに、特定の頂点 (すべてゼロのベクトルなど) に奇数の近傍があるとします。別の奇数次の頂点を見つける必要があります。この問題は NP であることに注意してください。つまり、解が与えられれば、回路を使用してその解が正しいことを検証できます。関数計算問題は、このグラフ検索問題に多項式時間で還元できる場合、PPA に属します。さらに、このグラフ検索問題がその問題に還元できる場合、問題はクラス PPA に対して 完全です。
関連クラス
PPAD は、有向グラフ上で定義される点を除いて、PPA と同様の方法で定義されます。PPADは PPA のサブクラスです。これは、 PPADを定義する対応する問題 (END OF THE LINE として知られています) が、上記の追加の奇数次頂点の検索 (基本的に、END OF THE LINE のエッジの方向を無視するだけ) に (簡単な方法で) 簡略化できるためです。
例
- PPAに対して完全であることが知られているSpernerの補題の非有向バージョンが存在する。[2]
- コンセンサス半減問題はPPAでは完全であることが知られている。[3]
- 3 次正則グラフ上の 2 番目のハミルトン サイクルを検索する問題はPPA のメンバーですが、PPA に対して完全であることは知られていません。
- 整数因数分解の問題からPPAに完全な問題へのランダム多項式時間還元が存在する。[4]
参考文献
- ^ Christos Papadimitriou (1994). 「パリティ議論の複雑さとその他の非効率的な存在証明について」(PDF) . Journal of Computer and System Sciences . 48 (3): 498–532. doi :10.1016/S0022-0000(05)80063-7. 2016-03-04 にオリジナル(PDF)からアーカイブ。2009-12-19に取得。
- ^ Michelangelo Grigni (1995). 「PPA のための完全なスペルナー補題」. Information Processing Letters . 77 (5–6): 255–259. CiteSeerX 10.1.1.63.9463 . doi :10.1016/S0020-0190(00)00152-6.
- ^ A. Filos-Ratsikas ; PW Goldberg ( 2018 ). 「コンセンサス半減はPPA完全」。第50回コンピューティング理論シンポジウム議事録。pp.51–64。arXiv : 1711.04503。doi : 10.1145 /3188745.3188880。
- ^ E. Jeřábek (2016). 「整数因数分解とモジュラー平方根」. Journal of Computer and System Sciences . 82 (2): 380–394. arXiv : 1207.5220 . doi :10.1016/j.jcss.2015.08.001.