多項式時間
計算量の問題で多項式時間のアルゴリズムという場合には、解くべき問題のサイズに対して処理時間が高々の多項式で表現できるオーダーであることを表す。 (絶対的な時間は含意されていない)
たとえばバブルソートの処理時間は要素数に対して要素の比較・交換を行う回数は高々 である。したがって、この場合の計算量のオーダーはO記法を用いてと表される。 またクイックソートの計算量のオーダーは である。
定義
多項式時間アルゴリズムと多項式時間問題の厳密な定義を述べる。
多項式時間アルゴリズム
Aをアルゴリズムとする。Aが以下の性質を満たす時、Aは多項式時間アルゴリズムであるという- ある多項式l(k)があって、任意のkと任意のkビットのデータxに対し、Aにxを入力した時にAが停止するまでのステップ数はl(k)以下である。
多項式時間問題とクラスP
Mを問題のクラスとする。 次が満たされる時Mは多項式時間で解けるという： あるアルゴリズムAとある多項式l(k)が存在して、任意のkと任意のm∈Mに対し、Aにmを入力するとAは問題mの答えをl(k)ステップ以内に出力する。deterministicなアルゴリズムで多項式時間で解ける判定問題のクラス全体の集合をPと表す。
関連項目
• 計算理論 • 指数関数時間 • 凖指数関数時間
