多項式時間アルゴリズム - 版の履歴

2008年11月12日 (水) 06:22にAlbeit-Kunによる

2008-11-12T06:22:23Z

Orsjwiki: "多項式時間アルゴリズム" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T02:15:52Z

"多項式時間アルゴリズム" を保護しました。 [edit=sysop:move=sysop]

2007年7月13日 (金) 16:02に124.144.188.143による

2007-07-13T16:02:36Z

122.17.2.240: 新しいページ: ''''【たこうしきじかんあるごりずむ (polynomial time algorithm)】''' どんな入力に対しても, 入力の長さの多項式時間で解を出力するアル...'

2007-07-13T05:12:30Z

新しいページ: ''''【たこうしきじかんあるごりずむ (polynomial time algorithm)】''' どんな入力に対しても, 入力の長さの多項式時間で解を出力するアル...'

新規ページ

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

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

← 古い版		2008年11月12日 (水) 06:22時点における版
2行目:		2行目:

	どんな入力に対しても, 入力の長さの多項式時間で解を出力するアルゴリズム. 例えば入力の長さ<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乗に比例する時間で問題を解く多項式時間アルゴリズムが存在しても, 現実には使い物にならないであろう.		どんな入力に対しても, 入力の長さの多項式時間で解を出力するアルゴリズム. 例えば入力の長さ<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:グラフ･ネットワーク\|たこうしきじかんあるごりずむ]]

← 古い版		2007年7月13日 (金) 16:02時点における版
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乗に比例する時間で問題を解く多項式時間アルゴリズムが存在しても, 現実には使い物にならないであろう.

← 古い版	2007年7月20日 (金) 02:15時点における版
(相違点なし)