MAX-3SAT とは

MAX-3SATは、コンピュータサイエンスの計算複雑度サブフィールドの問題です。それは複雑さ理論で考慮される決定問題であるブール充足可能性問題(SAT)を一般化する。これは次のように定義されます。
3-CNFの公式Φ(すなわち、句ごとに最大3つの変数を有する)が与えられた場合、最大数の句を満たす割当てを見つける。
MAX-3SATは、複雑さクラスMAXSNP(Papadimitriou pg.314に完全に示されている)に対する標準的な完全な問題です。