P (複雑さ)

計算複雑性理論において、PはPTIMEまたはDTIME ( n ^O(1) )とも呼ばれ、基本的な計算複雑性クラスです。これには、多項式量の計算時間、つまり多項式時間を使用して決定論的チューリングマシンで解決できるすべての決定問題が含まれます。

コブハムの論文では、 P は「効率的に解決可能な」または「扱いやすい」計算問題のクラスであるとされています。これは正確ではありません。実際には、P に属さない問題の中には実用的な解が存在するものもあれば、P に属さない問題もありますが、これは便利な経験則です。

言語LがP に属するのは、決定性チューリングマシン M が存在し、

• Mはすべての入力に対して多項式時間で実行される
• L内のすべてのxに対して、Mは1を出力する。
• Lに含まれないすべてのxに対して、Mは0を出力する。

Pはブール回路の一様族として見ることもできる。言語LがPに属するためには、ブール回路の一様族が多項式時間で存在し、その場合 のみである。${\displaystyle \{C_{n}:n\in \mathbb {N} \}}$

• すべての に対して、nビットを入力として受け取り、1ビットを出力する。${\displaystyle n\in \mathbb {N} }$${\displaystyle C_{n}}$
• L内のすべてのxについて、${\displaystyle C_{|x|}(x)=1}$
• Lに含まれないすべてのxについて、${\displaystyle C_{|x|}(x)=0}$

回路定義は、複雑度クラスを変更せずに、 対数空間均一族のみを使用するように弱めることができます。

Pには、線型計画法の決定版や最大マッチングを求める問題など、多くの自然な問題が含まれていることが知られています。2002年には、数が素数かどうかを判断する問題がPに含まれることが示されました。^{[1]関連する}関数の問題のクラスはFPです。

交互グラフ上のst連結性（または到達可能性）を含むいくつかの自然な問題はPに対して完全である。 ^[2] P完全問題に関する記事には、Pにおけるさらに関連する問題がリストされている 。

P の一般化はNPであり、これは多項式時間で実行される非決定性チューリングマシンによって決定可能な決定問題のクラスです。同様に、これは各「はい」インスタンスが多項式サイズの証明書を持ち、証明書が多項式時間決定性チューリングマシンによってチェックできる決定問題のクラスです。これが「いいえ」インスタンスに当てはまる問題のクラスはco-NPと呼ばれます。P は明らかに NP および co-NP のサブセットです。ほとんどの専門家はそれが適切なサブセットであると信じていますが^[3] 、この信念 (仮説)は証明されていません。もう 1 つの未解決の問題は、NP = co-NP であるかどうかです。P = co-P であるため^[4] 、否定の答えは を意味します。 ${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}$${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}$

P は、少なくともL （対数量のメモリ空間で決定可能な問題のクラス）と同じ大きさであることもわかっています。空間を使用する決定者は、可能な構成の総数である時間以上を使用することはできません。したがって、 L は P のサブセットです。もう 1 つの重要な問題は、L = P であるかどうかです。P = AL （交互チューリング マシンによって対数メモリで解決可能な問題の集合）であることはわかっています。P は、多項式空間で決定可能な問題のクラスであるPSPACEよりも大きくないこともわかっています。繰り返しますが、 P = PSPACE であるかどうかは未解決の問題です。要約すると、 ${\displaystyle O(\log n)}$${\displaystyle 2^{O(\log n)}=n^{O(1)}}$

${\displaystyle {\mathsf {L}}\subseteq {\mathsf {AL}}={\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {PSPACE}}\subseteq {\mathsf {EXPTIME}}.}$

ここで、EXPTIME は指数時間で解ける問題のクラスです。上記のすべてのクラスのうち、厳密な包含関係が知られているのは 2 つだけです。

• P は EXPTIME に厳密に含まれています。したがって、すべての EXPTIME 困難な問題は P の外部にあり、上記の P の右側の包含関係の少なくとも 1 つは厳密です (実際、3 つすべてが厳密であると広く信じられています)。
• L は厳密に PSPACE に含まれます。

P における最も難しい問題はP 完全問題です。

P の別の一般化はP/poly、つまり非一様多項式時間です。問題が P/poly に属する場合、入力の長さのみに依存するアドバイス文字列が与えられていれば、決定論的多項式時間で解決できます。ただし、NP とは異なり、多項式時間マシンは不正なアドバイス文字列を検出する必要はなく、検証器ではありません。P/poly は、BPPのすべてを含むほぼすべての実用的な問題を含む大きなクラスです。NP が含まれる場合、多項式階層は第 2 レベルに縮小されます。一方、決定不可能な問題の単項バージョンなど、いくつかの決定 不可能な問題を含む非実用的な問題もいくつか含まれています。

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

P はBQPに含まれていますが、この包含が厳密であるかどうかは不明です。

多項式時間アルゴリズムは合成に対して閉じています。直感的に言えば、関数呼び出しが定数時間であると仮定して多項式時間の関数を作成し、呼び出された関数自体が多項式時間を必要とする場合、アルゴリズム全体に多項式時間がかかります。この結果の 1 つは、P がそれ自体に対して低いことです。これは、P がマシンに依存しないクラスであると見なされる主な理由の 1 つでもあります。ランダム アクセスなど、多項式時間でシミュレートできるマシンの「機能」は、メインの多項式時間アルゴリズムと単純に合成して、より基本的なマシン上の多項式時間アルゴリズムに縮小できます。

P言語は反転、交差、和、連結、クリーネ閉包、逆準同型、相補に対しても閉じている。^[6]

いくつかの問題は多項式時間で解けることが知られていますが、それらを解くための具体的なアルゴリズムは知られていません。たとえば、ロバートソン-シーモア定理は、（たとえば）トーラスに埋め込むことができるグラフの集合を特徴付ける禁制マイナーの有限リストが存在することを保証します。さらに、ロバートソンとシーモアは、グラフが与えられたグラフをマイナーとして持つかどうかを判断するためのO( n ³ ) アルゴリズムがあることを示しました。これは、この問題に対する具体的なアルゴリズムが知られていないという事実にもかかわらず、与えられたグラフがトーラスに埋め込むことができるかどうかを判断するための多項式時間アルゴリズムが存在するという非構成的証明をもたらします 。

記述的複雑性において、Pは、順序構造上の、最小不動点演算子が追加された一階述語論理であるFO(LFP)で表現可能な問題として記述できる。記述的複雑性に関する1999年の教科書^[7]で、 Immermanはこの結果をVardi ^{[8]とImmerman [9]}に帰している。

2001年にPTIMEが（正の）範囲連結文法に対応することが発表されました。^[10]

Pは、決定問題ではない問題に対するアルゴリズムの複雑性クラスとして定義することもできます^[11]（たとえば、2-充足可能性インスタンスの解を多項式時間で見つけると、対応する決定問題に対する多項式アルゴリズムが自動的に得られます）。その場合、PはNPのサブセットではありませんが、P∩DECはNPのサブセットです。ここで、DECは決定問題のクラスです。

コーゼン^[12]は、コブハムとエドモンズが「一般的に多項式時間の概念を発明したとされている」と述べているが、ラビンも同時期に独立してこの概念を発明している（ラビンの論文^[13]は1966年の会議の1967年の議事録に掲載され、コブハムの論文^[14]は1964年の会議の1965年の議事録に掲載され、エドモンズの論文^[15]は1965年の雑誌に掲載されたが、ラビンはどちらにも言及しておらず、明らかに知らなかった）。コブハムは、効率的なアルゴリズムを特徴付ける堅牢な方法としてこのクラスを発明し、コブハムの論文につながった。しかし、HCポックリントンは1910年の論文^{[16] [17]}で、二次合同を解く2つのアルゴリズムを分析し、1つは「係数の対数の累乗に比例する」時間がかかることを観察した。これを「係数自体またはその平方根に比例する」時間がかかるものと対比し、多項式時間で実行されるアルゴリズムと（中程度に）指数時間で実行されるアルゴリズムを明確に区別した。

• エドモンズ、ジャック(1965)。「道、木、花」。カナダ数学ジャーナル。17 :449–467。doi :10.4153/ CJM - 1965-045-4。
• コブハム、アラン(1965)。「関数の本質的な計算難しさ」。バー・ヒレル、イェホシュア(編)。論理、方法論、科学哲学: 1964 年国際会議議事録。アムステルダム: 北ホラント。pp. 24–30。
• ラビン、マイケル O. (1967)。「オートマトンの数学的理論」。コンピュータサイエンスの数学的側面。応用数学シンポジウムの議事録。第 19 巻。アメリカ数学会。pp. 153–175。doi :10.1090/ psapm /019。
• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第2版。MIT Press and McGraw–Hill、2001年。ISBN 0-262-03293-7。セクション34.1: 多項式時間、pp. 971–979。 
• Papadimitriou, Christos H. (1994).計算複雑性. マサチューセッツ州レディング: Addison–Wesley. ISBN 978-0-201-53082-7。
• シプサー、マイケル(2006)。計算理論入門、第 2 版。Course Technology Inc. ISBN 978-0-534-95097-2。セクション7.2: クラスP、pp. 256–263。

• 複雑動物園：クラス P
• 複雑動物園: クラス P/poly