クラスMAX SNP

出典: ORWiki

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

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