DPLLアルゴリズムを使用したMAXSAT？

Question

最大SAT問題の最大値としてDPLLアルゴリズムMから戻ることは可能ですか？：

サンプルを持っています：

https://gist.github.com/davernig/e670bda7222D558817F2BA0E90EBCE66F

MAX-SATの結果を返すための再発を変更できますか？

リソース： https://en.wikipedia.org/wiki/dpll_algorithm

Answer 1

DPLLアルゴリズムはできるだけ多くの句を満たしようとしません。満足のいく割り当てがある場合は、DPLLが見つかります。それ以外の場合、DPLLは可能性がなくなるまで一連の一部の割り当てを試みてから、その後式を満たすことを宣言します。しかし、不満足な式の場合、DPLLは満足のいく可能性を証明するための途中で満足できる句の最大数を発見するという保証はありません。

MAXSAT問題は、インスタンスの最小限の満足不可能なサブフォーマル（MUSE）の検索に関連しています。一連の句がMUSであるかどうかを判断すると、DP完全な問題があります。これは単なるNP完全性よりも困難であると予想されているため、DPLLを変更するためにDPLLを修正することは実りあることになりそうもありません。クラスDPが $ \ delta ^ p_2 $ に含まれていることを考えると、DPLL（または関連するアルゴリズム）を呼び出す方式がMAXSATを生成する多項式回数結果。