P完了

計算複雑性理論では、決定問題がPに含まれ、かつ P 内のすべての問題が適切な簡約によってその問題に簡約できる場合、その問題は P完全(複雑性クラスPに対して完全) である。

P 完全決定問題の概念は、以下の分析に役立ちます。

• 効果的に並列化するのが困難な問題
• 限られたスペースでは解決が難しい問題です。

特に、多時間還元可能性よりも強い還元可能性の概念が考慮される場合。

使用される縮約の具体的な種類は様々であり、問​​題の正確な集合に影響する場合があります。一般的に、多項式時間縮約よりも強い縮約が使用されます。これは、 Pのすべての言語(空言語とすべての文字列の言語を除く) が多項式時間縮約の下でP完全であるためです。 NC縮約、つまり多項式数のプロセッサを備えた並列コンピュータで多対数時間で動作できる縮約を使用する場合、すべてのP完全な問題はNC の外側にあり、したがって、 NC  ≠  Pという証明されていない仮定の下では効果的に並列化できません。より強い対数空間縮約を使用する場合、これは当てはまりますが、さらに、L  ≠  Pという証明されていない弱い仮定の下では、すべてのP完全な問題がL の外側にあることがわかります。後者の場合、集合P完全は小さくなる可能性があります。

クラスPは、通常、シーケンシャル コンピュータで「扱いやすい」問題すべてから構成されると考えられていますが、このクラスNCは、並列コンピュータで効率的に解決できる問題から構成されています。これは、並列コンピュータをシーケンシャル マシンでシミュレートできるためです。 NC  =  Pであるかどうかは不明です。言い換えると、本質的にシーケンシャルである扱いやすい問題が存在するかどうかは不明です。P がNPと等しくないのではないかと広く疑われているのと同様に、 NC がPと等しくないのではないかと広く疑われています。

同様に、クラスL には、対数空間で順次コンピュータが解決できるすべての問題が含まれます。このようなマシンは、多項式数の構成を持つことができるため、多項式時間で実行されます。L  ≠  Pであると考えられます。つまり、多項式時間で解決できる問題の中には、対数空間以上のスペースを必要とするものもあります。

NP 完全問題を使用してP  =  NP問題を分析するのと同様に、P完全問題は、「おそらく並列化できない」または「おそらく本質的に順次的な」問題として見られ、同様の方法でNC  =  P問題を研究するのに役立ちます。 P完全問題のソリューションを並列化する効率的な方法を見つけると、NC  =  P が示されます。 これは、「超対数空間を必要とする問題」と考えることもできます。 P完全問題に対するログ空間ソリューション(ログ空間削減に基づく定義を使用) は、 L  =  Pを意味します。

この背後にあるロジックは、 NP完全問題に対する多項式時間ソリューションがP  =  NPを証明するというロジックに類似しています。つまり、P内の任意の問題から問題 A へのNC還元と、 A に対するNCソリューションがある場合、NC  =  Pです。同様に、 P内の任意の問題から問題 A への対数空間還元と、 A に対する対数空間ソリューションがある場合、L  =  Pです。

対数空間多対一縮約における最も基本的なP完全問題は次のとおりです。チューリングマシン 、そのマシンへの入力 x、および数T (単項で記述) が与えられた場合、そのマシンは最初のTステップ以内にその入力で停止しますか? P 内の任意の x について、それを多項式時間で受け入れるチューリングマシンのエンコード、 x 自体のエンコード、およびチューリングマシンが、を決定する操作に関する多項式時間境界である p に対応するステップ数を出力します。マシン M が x でステップ以内に停止するのは、x が L 内にある場合のみです。明らかに、シーケンシャルコンピュータの一般的なシミュレーション (つまり、チューリングマシンのチューリングマシンシミュレーション) を並列化できる場合、そのコンピュータで実行される任意のプログラムを並列化できます。この問題がNCである場合、他のすべての問題もP内にあります。ステップ数がバイナリで記述されている場合、問題はEXPTIME 完全です。この問題は、 P完全性の理論における一般的なトリックを示しています。並列マシンで問題を素早く解けるかどうかは、あまり関心がありません。関心があるのは、並列マシンが逐次型マシンよりもはるかに速く問題を解くかどうかだけです。したがって、逐次型バージョンがPに含まれるように問題を言い換える必要があります。この問題ではT を単項で記述する必要があったのはそのためです。数Tが2 進数 ( n個の 1 と 0 の文字列、n  = log  T )として記述される場合、明らかな逐次型アルゴリズムは 2 ^{n の}時間がかかります。一方、T が単項数 ( n個の 1 の文字列、n  =  T ) として記述される場合、n の時間しかかかりません。T を2 進数ではなく単項で記述することで、明らかな逐次型アルゴリズムを指数時間から線形時間に短縮しました。これにより、逐次型の問題はPに含まれます。そして、並列化可能な場合に限り、 NCに含まれます。${\displaystyle M}$${\displaystyle \langle M,x,T\rangle }$${\displaystyle L}$${\displaystyle T=p(|x|)}$${\displaystyle M_{L}}$${\displaystyle L}$${\displaystyle \langle M,x,p(|x|)\rangle }$${\displaystyle p(|x|)}$

他の多くの問題はP完全であることが証明されており、したがって本質的に順次的であると広く信じられています。これらには、与えられたまま、または決定問題の形式で、少なくとも対数空間削減の下で P完全である次の問題が含まれます。

• 回路値問題(CVP) -回路、回路への入力、および回路内の 1 つのゲートが与えられた場合、そのゲートの出力を計算します。
• CVP の制限されたケース - CVP と同様ですが、各ゲートには 2 つの入力と 2 つの出力 (F と Not F) があり、他のすべての層は AND ゲートで、残りは OR ゲート (または、すべてのゲートが NAND ゲート、またはすべてのゲートが NOR ゲート) であり、ゲートの入力は直前の層から取得されます。
• 線形計画法– 線形不等式制約の下で線形関数を最大化する
• 辞書式優先の深さ優先探索順序 –固定順序の隣接リストとノードuおよびv を持つグラフが与えられた場合、隣接リストの順序によって誘導される深さ優先探索で、頂点u は頂点vより前に訪問されるでしょうか?
• 文脈自由文法のメンバーシップ -文脈自由文法と文字列が与えられた場合、その文字列はその文法によって生成できますか?
• ホーン充足可能性-ホーン節の集合が与えられたとき、それらを満たす変数割り当てはあるか? これはブール充足可能性問題のPバージョンです。
• 生命ゲーム - Conway の生命ゲームの初期構成、特定のセル、および時間T (単項式) が与えられた場合、そのセルはTステップ後に生きているでしょうか?
• LZW (アルゴリズム) (1978 パラダイム) データ圧縮 - 文字列sとtが与えられた場合、 s をLZ78 方式で圧縮すると、 t が辞書に追加されますか? ( gzipなどのLZ77圧縮の場合、問題は「t はsに含まれているか?」に簡略化されるため、これははるかに簡単になります。)
• 部分型の型推論-ラムダ計算からの型指定されていない項が与えられた場合、この項に部分型があるかどうかを判断します。

上記の言語のほとんどは、一様多対一縮約、DLOGTIME 縮約、多重対数射影 などのさらに強力な縮約概念の下ではP完全です。${\displaystyle AC^{0}}$

Pにおける与えられた問題がP完全であることを証明するためには、通常、既知のP完全問題を与えられた問題に 簡略化しようとします。

1999年、Jin-Yi CaiとD. Sivakumarは、Ogiharaの研究を基に、P完全なスパース言語が存在する場合、L  =  Pであることを示した。^[1]

P完全問題は、異なる時間計算量で解ける場合があります。たとえば、回路値問題は、トポロジカルソートによって線形時間で解くことができます。もちろん、 P完全問題への還元は異なる時間計算量を持つ可能性があるため、この事実はPのすべての問題が線形時間で解けることを意味するものではありません。

• Greenlaw、Raymond、James Hoover、Walter Ruzzo。1995 年。並列計算の限界、P 完全性理論。ISBN 0-19-508591-4。—理論を展開し、96 個の P 完全問題をカタログ化します。 
• 宮野悟、白石修二、翔大貴好。P-Complete 問題のリスト。九州大学、RIFIS-TR-CS-17。 1990年12月。