P集合全体の集合

決定的な多項式アルゴリズムで解ける決定問題のクラス

多項式アルゴリズムは、多項式時間で解けるアルゴリズム

実際の計算機で解くことができる問題はだいたいコレに属している

全数探索すると基本的に指数時間になってまうから、がんばって多項式時間で解けるアルゴリズムを見つけてクラスPに入れていこうな！って感じなんかな

\mathrm{P}\subseteq\mathrm{NP}という関係がある

Pに属す問題は、解くのも検証も多項式時間

クラスNPに属す問題は、正解の検証が多項式時間

定義

決定性単一テープチューリングマシンによって多項式時間で判定できる言語のクラスのことをPとする

P=\bigcup_{k(\gt0)} \mathrm{TIME}(n^k)=\mathrm{TIME}(n^{O(1)})

\mathrm{TIME}(t(n))は、時間計算量がO(t(n))であるアルゴリズムを持つ問題の集合

何らかの問題があるときに、クラスPに属することを示すための手順

入力サイズnに対して、そのアルゴリズムで実行されるステップ数の多項式の上界を与える

各ステップが、決定性計算モデル上で多項式時間で実現できることを確認する

クラスPに属する問題の例

問題が云々というより、どういうアルゴリズムで導くかで、クラスPに属するかどうかが決まる

一つでも属する解法が見つかれば、Pに属すると言える

PATH問題 ref p.309

グラフGとその中の節点s,tがあるとき、sからtへのパスが存在するかどうかを判定する

2つの数が与えられたときに、これが互いに素かどうかを判定する ref p.311

2つの数をすべての可能な数で割っていけば全探索になってしまい指数時間かかってしまう

ユークリッドの互除法などを使えば多項式時間に収まる

全ての文脈自由言語はクラスPに属する ref p.313

動的計画法を用いる

\mathrm{equal}_{01}=\{u\in\{0,1\}^\ast|u内の0と1の出現回数が等しい\}　

これを計算するチューリングマシンの、計算ステップ数は入兎力の長さnに対し、常に2n^2+1以下になる

参考