Karloff–Zwick algorithm とは

計算複雑性理論におけるKarloff-Zwickアルゴリズムは、入力としてMAX-3SATブール充足可能性問題のインスタンスを取るランダム化近似アルゴリズムである。インスタンスが充足可能である場合、見つけられた課題の予想される重みは、少なくとも最適の7/8です。これは、アルゴリズムが任意のMAX-3SATインスタンスで同等に良好に実行するという強力な証拠(数学的証明ではない)を提供します。 Howard KarloffとUri Zwickはアルゴリズムを1997年に発表しました。
入力3SAT式のすべての句が正確に3つのリテラルを持つことが保証されている関連するMAX-E3SAT問題については、各変数に真理値を無作為に無作為に割り当てる単純なランダム化近似アルゴリズムは、すべての節の7/8を満たします元の式が充足可能であるかどうかにかかわらず、期待どおりではありません。さらに、この単純なアルゴリズムは、条件付き期待値の方法を用いて容易に逆ランダム化することもできる。しかし、Karloff-Zwickアルゴリズムでは、入力式にすべての句に3つのリテラルが含まれるように制限する必要はありません。
JohanHåstadは、P≠NPと仮定すると、MAX 3SATの多項式時間アルゴリズムは、各節が満足できるインスタンスに制限されていても、7/8を超える性能比を達成することができないことを示した厳密に3つのリテラルを含む。したがって、この意味では、Karloff-Zwickアルゴリズムと上記の単純アルゴリズムの両方が最適です。