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} \}}$、したがって

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

回路定義は、複雑性クラスを変更することなく、対数空間一様族のみを使用するように緩和することができる。

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

P にはいくつかの自然な問題が完全であり、交代グラフ上のst-連結性(または到達可能性) などが含まれます^{[ 2 ]。P}完全問題に関する記事には、P のその他の関連問題がリストされています。

P の一般化はNPであり、これは多項式時間で動作する非決定性チューリングマシンによって決定可能な決定問題のクラスです。言い換えれば、各「はい」インスタンスが多項式サイズの証明書を持ち、証明書が多項式時間で動作する決定性チューリングマシンによって検証できる決定問題のクラスです。「いいえ」インスタンスに対してこれが成り立つ問題のクラスはco-NPと呼ばれます。P は自明に NP および co-NP の部分集合です。ほとんどの専門家は、P は真部分集合であると考えていますが、^{[ 3 ]}この考え (${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}$仮説）は未証明のままである。もう1つの未解決問題は、NP  =  co-NP かどうかである。P = co-P なので、^{[ 4 ]}否定的な答えは、${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}$。

P は、対数量のメモリ空間で決定可能な問題のクラスであるLと少なくとも同程度の大きさであることが知られています。${\displaystyle O(\log n)}$スペースは以下を使用できる$2^{O(\log n)}=n^{O(1)}}$時間、これは可能な構成の総数であるため、L は P の部分集合です。もう 1 つの重要な問題は、L = P かどうかです。P = AL、つまり交互チューリングマシンによって対数メモリで解ける問題の集合はわかっています。P は、多項式空間で決定可能な問題のクラスであるPSPACEより大きくないこともわかっています。PSPACE は、サビッチの定理により NPSPACE と同等です。繰り返しますが、P = PSPACE かどうかは未解決の問題です。まとめると次のようになります。

${\displaystyle {\mathsf {L}}\subseteq {\mathsf {AL}}={\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {PSPACE}}={\mathsf {NPSPACE}}\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 レベルに縮退します。一方で、 P/poly には、任意の決定不能問題の単項バージョンなどの決定不能問題を含む、いくつかの非実用的な問題も含まれています。

1999年、Jin-Yi CaiとD. Sivakumarは、 Mitsunori Ogiharaの研究に基づいて、 P-完全な疎言語が存在するならば、L = Pであることを示した。^{[ 5 ]}

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

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

P の言語は、反転、交差、和集合、連結、クリーネ閉包、逆準同型、および補元に関して閉じている。^{[ 6 ]}

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

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

1992年にBellantoniとCookは、 FPの別の特徴付け^{[ 10 ]}を与え、安全な再帰スキームを使用して多項式時間で計算可能な関数を定義し、暗黙的計算複雑性の枠組み内でマシンに依存しない構造的定義を提供した。^{[ 11 ]}

2001年に、PTIMEは（正の）範囲連結文法に対応することが発表された。^{[ 12 ]}

P は、決定問題ではない問題のアルゴリズム的複雑性クラスとしても定義できます^{[ 13 ]} (例えば、2-充足可能性インスタンスの解を多項式時間で見つけると、対応する決定問題に対する多項式アルゴリズムが自動的に得られるにもかかわらず)。この場合、P は NP の部分集合ではありませんが、${\displaystyle P\cap DEC}$は、${\displaystyle DEC}$これは決定問題のクラスである。

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

• 「計算複雑性理論」の項目ウォルター・ディーン著、『スタンフォード哲学百科事典』、2021年秋号
• StackOverflow。「複雑性理論 - なぜ co-P = P なのか」。Stack Overflow 。 2025年11月15日取得。
• 複雑性動物園：クラスP
• 複雑性動物園：クラスP/ポリ