MAX 2-SATは2 SATに還元可能な多項式の時間ですか？

Question

2 SATが多項式時間で解決可能であり、2 satはNPハードです。

この文について問題があります。 MAX 2-SATは2 SATに多項式 - 時間を和らげます。あなたは私にどのようにしてどのように見えるかを説明できますか？それについての唯一の注意が必要ですが、証明は必要ありません。

Answer 1

ここに混乱があると思います。MAX-2-SATはNP-HARD（そしてその決定バージョンはNP完了）であり、2 SATはPにあり、したがってNPでもまたはNPである。つまり、2 SATが（決定バージョンの）MAX-2-SATから多項式 - 時間で還元可能であることを意味します。P= NPの場合を除き、逆は当てはまりません。

$ \ phi $ を $ m $ 句を持つ2 SAT式になります。 インスタンス $ \ phi $ を縮小したい場合は、MAX-2-SATの2-SATから（Decision Version）MAX-2-SATまで、この場合、これは単純にチェックするかどうかを確認します。少なくとも $ m $ （つまり、すべての）句の $¥PHI $ の句は満足のいく可能性があります。