多項式時間アルゴリズム

【たこうしきじかんあるごりずむ (polynomial time algorithm)】

どんな入力に対しても, 入力の長さの多項式時間で解を出力するアルゴリズム. 例えば入力の長さ$n$に対して, $n^2$や$n^{100}$は多項式であるが, $2^n$や$n^{\log n}$や$\log n^{\log n}$は多項式ではない. ある問題に対して多項式時間アルゴリズムが存在しないことが示せれば, その問題は「手に負えない」といってよい. しかし入力の長さの1000乗に比例する時間で問題を解く多項式時間アルゴリズムが存在しても, 現実には使い物にならないであろう.