「多項式時間アルゴリズム」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: ''''【たこうしきじかんあるごりずむ (polynomial time algorithm)】''' どんな入力に対しても, 入力の長さの多項式時間で解を出力するアル...')
 
 
(2人の利用者による、間の2版が非表示)
1行目: 1行目:
 
'''【たこうしきじかんあるごりずむ (polynomial time algorithm)】'''
 
'''【たこうしきじかんあるごりずむ (polynomial time algorithm)】'''
  
−
どんな入力に対しても, 入力の長さの多項式時間で解を出力するアルゴリズム. 例えば入力の長さ$n$に対して, $n^2$や$n^{100}$は多項式であるが, $2^n$や$n^{\log n}$や$\log n^{\log n}$は多項式ではない. ある問題に対して多項式時間アルゴリズムが存在しないことが示せれば, その問題は「手に負えない」といってよい. しかし入力の長さの1000乗に比例する時間で問題を解く多項式時間アルゴリズムが存在しても, 現実には使い物にならないであろう.
+
どんな入力に対しても, 入力の長さの多項式時間で解を出力するアルゴリズム. 例えば入力の長さ<math>n \,</math>に対して, <math>n^2 \,</math>や<math>n^{100} \,</math>は多項式であるが, <math>2^n \,</math>や<math>n^{\log n} \,</math>や<math>\log n^{\log n} \,</math>は多項式ではない. ある問題に対して多項式時間アルゴリズムが存在しないことが示せれば, その問題は「手に負えない」といってよい. しかし入力の長さの1000乗に比例する時間で問題を解く多項式時間アルゴリズムが存在しても, 現実には使い物にならないであろう.
 +
 
 +
[[Category:組合せ最適化|たこうしきじかんあるごりずむ]]
 +
 
 +
[[Category:グラフ･ネットワーク|たこうしきじかんあるごりずむ]]

2008年11月12日 (水) 15:22時点における最新版

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

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

「https://orsj-ml.org/orwiki/wiki/index.php?title=多項式時間アルゴリズム&oldid=10679」から取得