多項式時間

デジタル大辞泉

たこうしき‐じかん〔タカウシキ‐〕【多項式時間】

読み方：たこうしきじかん

コンピューターの計算理論において、問題を解く上で必要な計算時間が、問題の規模をn、定数をkとしたとき、nの多項式すなわちn^kで表されるもの。問題の規模とは組み合わせの要素や繰り返しの数を指し、計算時間の上限を容易に見積もることができる。→指数関数時間

ウィキペディア

多項式時間

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/04/16 02:24 UTC 版)

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

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

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

定義

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

多項式時間アルゴリズム

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

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

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

多項式時間アルゴリズムが存在する問題とクラスP

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

関連項目

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

ウィキペディア小見出し辞書

多項式時間

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/28 15:48 UTC 版)

「グラフ彩色」の記事における「多項式時間」の解説

あるグラフが2色で彩色可能かどうかを決定する問題は、そのグラフが2部グラフかどうかの決定問題と等価であり、幅優先探索を使って多項式時間で解ける。より一般化すれば、パーフェクトグラフの彩色数と具体的な彩色は半正定値計画法を使って多項式時間で計算できる。森、弦グラフ、閉路グラフ、車輪グラフ、梯子グラフといった種類のグラフは彩色多項式がわかっているので、多項式時間での評価が可能である。