Proofs and Certificates for Max-SAT (Extended Abstract)

Matthieu Py, Mohamed Sami Cherif, Djamal HabetIJCAI 2023 · DOI

TL;DR

This paper introduces MS-Builder, a novel tool that generates verifiable "certificates" for Max-SAT problems. These certificates, in the form of equivalence-preserving transformations, bridge the gap between standard SAT refutations and Max-SAT proofs, offering a more robust way to validate Max-SAT solver results.

What Problem Does This Paper Address?

The Maximum Satisfiability (Max-SAT) problem is a crucial extension of the Satisfiability (SAT) problem, aiming to find an assignment that satisfies the maximum possible number of clauses in a given Boolean formula. While SAT solvers can produce refutations (proofs of unsatisfiability), adapting these refutations to the Max-SAT context has been a long-standing challenge. Specifically, directly translating a SAT refutation into a Max-SAT refutation often leads to a significant, potentially exponential, increase in proof size, making it impractical. This paper addresses this gap by developing methods to efficiently transform SAT refutations into Max-SAT refutations, thereby enabling the creation of verifiable certificates for Max-SAT solutions.

Methods

The core of this work lies in developing techniques to adapt standard SAT resolution refutations into Max-SAT refutations. The authors introduce a modified Max-SAT resolution rule that includes a "split rule," allowing for the generation of two clauses from one, which helps in preserving Max-SAT equivalence.

Key methodological contributions include:

  • Adapting Resolution Refutations: The paper presents theoretical results showing that SAT refutations can be transformed into Max-SAT refutations with a linear increase in size for specific types of refutations (read-once, semi-read-once, tree-like regular, tree-like, and semi-tree-like). For general, unrestricted refutations, an exponential blow-up is possible but a method is provided.
  • MS-Builder Tool: This is a practical implementation that iteratively calls a SAT oracle to obtain resolution refutations. These refutations are then adapted for Max-SAT using the developed techniques. The process continues until the formula becomes satisfiable, at which point the accumulated transformations form a certificate.
  • MS-Checker Tool: A companion tool designed to verify the validity of the certificates generated by MS-Builder, ensuring their correctness.

Datasets

The paper evaluates MS-Builder on the complete track benchmarks from the 2020 Max-SAT Evaluation. These benchmarks consist of both unweighted and weighted (partial) Max-SAT instances.

Key Insights and Ideas

  • Bridging the SAT-MaxSAT Divide: The most significant insight is that the gap between SAT and Max-SAT refutations is not insurmountable. By carefully adapting resolution rules, it's possible to create efficient Max-SAT proofs, which is crucial for building trust in Max-SAT solvers.
  • The Power of the Split Rule: The introduction of the split rule in Max-SAT resolution is a key enabler for transforming SAT refutations. It provides a mechanism to handle clauses that might be problematic in a direct translation.
  • Practical Implications of Proof Size: The paper highlights that while general transformations are possible, the size of the resulting Max-SAT refutation is a critical factor. Achieving linear-sized transformations for many common refutation types makes the certificate generation practical.
  • Empirical Differences: The study reveals interesting empirical differences between unweighted and weighted Max-SAT instances. Weighted instances tend to yield a lower percentage of "easy" refutation types (read-once and semi-read-once), suggesting they are inherently harder to prove.

Key Results

  • Theoretical Guarantees: The paper provides theoretical guarantees for transforming various types of SAT refutations into Max-SAT refutations. For semi-read-once, tree-like regular, tree-like, and semi-tree-like refutations, the Max-SAT refutation size is linear with respect to the original SAT refutation size. For unrestricted refutations, a linear transformation is possible but with a potential exponential blow-up in size.
  • MS-Builder Performance: MS-Builder successfully generated full proofs for a significant number of instances from the 2020 Max-SAT Evaluation benchmarks. Specifically, it succeeded on 163 out of 576 unweighted instances and 144 out of 600 weighted instances within a 1-hour time limit and 16GB memory constraint.
  • Partial Proofs: For many other instances, MS-Builder was able to generate proofs that covered at least half of the optimum cost, demonstrating its utility even when full proofs are not achievable within the given constraints.
  • Refutation Type Distribution: The experiments showed that read-once and semi-read-once refutations were prevalent (83.7%) in unweighted instances, whereas weighted instances showed a more diverse distribution, with only 35.60% being of these types.

Limitations and Future Work

  • Unrestricted Refutations: While the paper provides a method to adapt unrestricted SAT refutations to Max-SAT, the potential for exponential blow-up in proof size remains a limitation. Future work could explore more efficient ways to handle these cases.
  • Scalability for Complex Instances: Although MS-Builder performed well on many instances, the time and memory constraints of the evaluation might have limited its success on the most challenging problems. Further optimization of the MS-Builder and MS-Checker tools could improve scalability.
  • Exploration of Other Proof Systems: The paper focuses on resolution-based refutations. Future research could investigate adapting other SAT proof systems to Max-SAT or explore entirely new Max-SAT proof systems.
  • Broader Benchmark Evaluation: While the 2020 Max-SAT Evaluation benchmarks are standard, evaluating MS-Builder on a wider range of real-world Max-SAT problems could provide further insights into its practical applicability.

Summary updated

BibTeX
@inproceedings{py2023proofs,
  author = {Matthieu Py and Mohamed Sami Cherif and Djamal Habet},
  title = {{Proofs and Certificates for Max-SAT (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/787},
}

Loading related content...

Figure