クラスP
決定的な多項式アルゴリズムで解ける決定問題のクラス 多項式アルゴリズムは、多項式時間で解けるアルゴリズム 実際の計算機で解くことができる問題はだいたいコレに属している
全数探索すると基本的に指数時間になってまうから、がんばって多項式時間で解けるアルゴリズムを見つけてクラスPに入れていこうな！って感じなんかなmrsekut.icon
$ \mathrm{P}\subseteq\mathrm{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に属するかどうかが決まるmrsekut.icon
一つでも属する解法が見つかれば、Pに属すると言える
PATH問題 ref 『計算理論の基礎 3』.icon p.309
グラフ$ Gとその中の節点$ s,tがあるとき、$ sから$ tへのパスが存在するかどうかを判定する
2つの数が与えられたときに、これが互いに素かどうかを判定する ref 『計算理論の基礎 3』.icon p.311
2つの数をすべての可能な数で割っていけば全探索になってしまい指数時間かかってしまう 全ての文脈自由言語はクラスPに属する ref 『計算理論の基礎 3』.icon p.313 $ \mathrm{equal}_{01}=\{u\in\{0,1\}^\ast|u内の0と1の出現回数が等しい\}
これを計算するチューリングマシンの、計算ステップ数は入兎力の長さ$ nに対し、常に$ 2n^2+1以下になる
参考