OR事典

多項式時間アルゴリズム

読み方：たこうしきじかんあるごりずむ
【英】：polynomial time algorithm

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

「OR事典」の他の用語

組合せ最適化：	動的木  動的計画  多面体理論  多項式時間アルゴリズム  巡回セールスマン問題  整数計画  施設配置問題
グラフ･ネットワーク：	基族  基本分割  多品種フロー  多項式時間アルゴリズム  安定結婚問題  完全グラフ  局所点連結度