多項式時間アルゴリズムとは何？わかりやすく解説 Weblio辞書

多項式時間アルゴリズム

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

「OR事典」の他の用語

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

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

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

「多項式時間」の続きの解説一覧

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

「多項式時間」の記事における「多項式時間アルゴリズム」の解説

Aをアルゴリズムとする。Aが以下の性質を満たす時、Aは多項式時間アルゴリズムであるというある多項式l(k)があって、任意のkと任意のkビットのデータxに対し、Aにxを入力した時にAが停止するまでのステップ数はl(k)以下である。なお「多項式時間アルゴリズム」と言った場合、決定的アルゴリズムのみを多項式時間アルゴリズムとして認める場合と、確率的アルゴリズムをも許す場合とがある。

※この「多項式時間アルゴリズム」の解説は、「多項式時間」の解説の一部です。
「多項式時間アルゴリズム」を含む「多項式時間」の記事については、「多項式時間」の概要を参照ください。

ウィキペディア小見出し辞書の「多項式時間アルゴリズム」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。お問い合わせ。

多項式時間アルゴリズムと同じ種類の言葉


	Copyright (C) 2024 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアの多項式時間 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
	Text is available under GNU Free Documentation License (GFDL). Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの多項式時間 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。