多項式時間

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "多項式時間" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2016年9月)

多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。

多項式時間のアルゴリズムとは、解くべき問題の入力サイズ${\displaystyle n}$に対して、処理時間の上界として${\displaystyle n}$の多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。

たとえばバブルソートの処理時間は要素数${\displaystyle n}$に対して要素の比較・交換を行う回数は高々 ${\displaystyle {\frac {1}{2}}n(n-1)}$ である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いて${\displaystyle O({n^{2}})}$と表される。 またクイックソートの期待計算量のオーダーは${\displaystyle O(n\log n)}$、最悪計算量のオーダーは${\displaystyle O({n^{2}})}$である。

多項式時間アルゴリズムと多項式時間アルゴリズムが存在する問題クラスについて、簡単に記す。

Aをアルゴリズムとする。Aが以下の性質を満たす時、Aは多項式時間アルゴリズムであるという

ある多項式l(k)があって、任意のkと任意のkビットのデータxに対し、Aにxを入力した時にAが停止するまでのステップ数はl(k)以下である。

なお「多項式時間アルゴリズム」と言った場合、決定的アルゴリズムのみを多項式時間アルゴリズムとして認める場合と、確率的アルゴリズムをも許す場合とがある。

決定的な多項式時間アルゴリズム（上で定義した）で解ける判定問題の集合をクラスPと呼ぶ（判定問題以外の問題はクラスPに含まれないことに注意）。

• 計算量理論
• 定数時間
• 指数関数時間
• 多項式時間変換
• 凖指数関数時間
• 時間計算量