「クラスMAX SNP」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: ''''【くらすまっくすえすえぬぴー (class MAX SNP)】''' 厳密解だけでなく, よい近似解すら求めるのが困難な問題のクラスの1つ. 厳密解...')
 
 
(2人の利用者による、間の2版が非表示)
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>に限界がある.
 +
 
 +
[[Category:組合せ最適化|くらすまっくすえすえぬぴー]]

2008年11月8日 (土) 19:51時点における最新版

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

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