クラスMAX SNP - 版の履歴

2008年11月8日 (土) 10:51にAlbeit-Kunによる

2008-11-08T10:51:18Z

Orsjwiki: "クラスMAX SNP" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T00:33:48Z

"クラスMAX SNP" を保護しました。 [edit=sysop:move=sysop]

2007年7月11日 (水) 18:02に131.112.125.103による

2007-07-11T18:02:18Z

122.17.2.240: 新しいページ: ''''【くらすまっくすえすえぬぴー (class MAX SNP)】''' 厳密解だけでなく, よい近似解すら求めるのが困難な問題のクラスの1つ. 厳密解...'

2007-07-11T13:30:00Z

新しいページ: ''''【くらすまっくすえすえぬぴー (class MAX SNP)】''' 厳密解だけでなく, よい近似解すら求めるのが困難な問題のクラスの1つ. 厳密解...'

新規ページ

'''【くらすまっくすえすえぬぴー (class MAX SNP)】'''

厳密解だけでなく, よい近似解すら求めるのが困難な問題のクラスの1つ. 厳密解を求めることが困難な問題であっても, 任意の正定数$\epsilon$を与えれば, $(1/\epsilon)$と入力の大きさの多項式時間で, 近似率$\epsilon$の解を求められる場合がある. しかしMAXSNP困難な問題は, $\mbox{P}\neq \mbox{NP}$という仮定の下では, 多項式時間で近似率$\epsilon$の近似解を求められるような$\epsilon$に限界がある.

← 古い版		2008年11月8日 (土) 10:51時点における版
2行目:		2行目:

	厳密解だけでなく, よい近似解すら求めるのが困難な問題のクラスの1つ. 厳密解を求めることが困難な問題であっても, 任意の正定数<math>\epsilon\,</math>を与えれば, <math>(1/\epsilon)\,</math>と入力の大きさの多項式時間で, 近似率<math>\epsilon\,</math>の解を求められる場合がある. しかしMAXSNP困難な問題は, <math>\mbox{P}\neq \mbox{NP}\,</math>という仮定の下では, 多項式時間で近似率<math>\epsilon\,</math>の近似解を求められるような<math>\epsilon\,</math>に限界がある.		厳密解だけでなく, よい近似解すら求めるのが困難な問題のクラスの1つ. 厳密解を求めることが困難な問題であっても, 任意の正定数<math>\epsilon\,</math>を与えれば, <math>(1/\epsilon)\,</math>と入力の大きさの多項式時間で, 近似率<math>\epsilon\,</math>の解を求められる場合がある. しかしMAXSNP困難な問題は, <math>\mbox{P}\neq \mbox{NP}\,</math>という仮定の下では, 多項式時間で近似率<math>\epsilon\,</math>の近似解を求められるような<math>\epsilon\,</math>に限界がある.
		+
		+	[[Category:組合せ最適化\|くらすまっくすえすえぬぴー]]

← 古い版		2007年7月11日 (水) 18:02時点における版
1行目:		1行目:
	'''【くらすまっくすえすえぬぴー (class MAX SNP)】'''		'''【くらすまっくすえすえぬぴー (class MAX SNP)】'''

−	厳密解だけでなく, よい近似解すら求めるのが困難な問題のクラスの1つ. 厳密解を求めることが困難な問題であっても, 任意の正定数$\epsilon$を与えれば, $(1/\epsilon)$と入力の大きさの多項式時間で, 近似率$\epsilon$の解を求められる場合がある. しかしMAXSNP困難な問題は, $\mbox{P}\neq \mbox{NP}$という仮定の下では, 多項式時間で近似率$\epsilon$の近似解を求められるような$\epsilon$に限界がある.	+	厳密解だけでなく, よい近似解すら求めるのが困難な問題のクラスの1つ. 厳密解を求めることが困難な問題であっても, 任意の正定数<math>\epsilon\,</math>を与えれば, <math>(1/\epsilon)\,</math>と入力の大きさの多項式時間で, 近似率<math>\epsilon\,</math>の解を求められる場合がある. しかしMAXSNP困難な問題は, <math>\mbox{P}\neq \mbox{NP}\,</math>という仮定の下では, 多項式時間で近似率<math>\epsilon\,</math>の近似解を求められるような<math>\epsilon\,</math>に限界がある.

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