多項式時間
 |
多項式時間（たこうしきじかん、polynomial time）とは、計算理論において、計算問題を解くアルゴリズムの計算時間が入力サイズの多項式で抑えられることを指す。
すなわち、入力サイズを としたとき、計算時間が の定数次数の多項式以内に収まる場合である。この概念はアルゴリズムの効率性評価や、効率的に解ける問題の分類に用いられ、問題規模が大きくなっても計算時間の増加が比較的緩やかであることから、一般に実用的に計算可能な問題を示す代表的な基準とされる。
たとえばバブルソートの処理時間は要素数に対して要素の比較・交換を行う回数は高々 である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてと表される。 またクイックソートの期待計算量のオーダーは、最悪計算量のオーダーはである。
定義
[編集]多項式時間アルゴリズムと多項式時間アルゴリズムが存在する問題クラスについて、簡単に記す。
多項式時間アルゴリズム
[編集]Aをアルゴリズムとする。Aが以下の性質を満たす時、Aは多項式時間アルゴリズムであるという。ここで｜x｜はxのビット長であり、｜x｜=kである。
- 任意の正の整数kと任意のkビットのデータxに対し、Aにxを入力した時にAが停止するまでのステップ数をT(x)とする。T(x)≦p(｜x｜)がすべての入力xに対して成り立つような多項式pが少なくとも1つ存在する。
なお「多項式時間アルゴリズム」と言った場合、決定的アルゴリズムのみを多項式時間アルゴリズムとして認める場合と、確率的アルゴリズムをも許す場合とがある。
多項式時間アルゴリズムが存在する問題とクラスP
[編集]決定的な多項式時間アルゴリズム（上で定義した）で解ける判定問題の集合をクラスPと呼ぶ（判定問題以外の問題はクラスPに含まれないことに注意）。