クラスMAX SNP

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

厳密解だけでなく, よい近似解すら求めるのが困難な問題のクラスの1つ. 厳密解を求めることが困難な問題であっても, 任意の正定数$\epsilon \,$を与えれば, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (1/\epsilon)\,} と入力の大きさの多項式時間で, 近似率構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \epsilon\,} の解を求められる場合がある. しかしMAXSNP困難な問題は, ${\mbox{P}}\neq {\mbox{NP}}\,$という仮定の下では, 多項式時間で近似率$\epsilon \,$の近似解を求められるような$\epsilon \,$に限界がある.