Proofs and Certificates for Max-SAT (Extended Abstract)

Matthieu Py; Mohamed Sami Cherif; Djamal Habet

IJCAI 2023poster0 citations

Proofs and Certificates for Max-SAT (Extended Abstract)

Matthieu Py, Mohamed Sami Cherif, Djamal Habet

Abstract

In this paper, we present a tool, called MS-Builder, which generates certificates for the Max-SAT problem in the particular form of a sequence of equivalence-preserving transformations. To generate a certificate, MS-Builder iteratively calls a SAT oracle to get a SAT resolution refutation which is handled and adapted into a sound refutation for Max-SAT. In particular, the size of the computed Max-SAT refutation is linear with respect to the size of the initial refutation if it is semi-read-once, tree-like regular, tree-like or semi-tree-like. Additionally, we propose an extendable tool, called MS-Checker, able to verify the validity of any Max-SAT certificate using Max-SAT inference rules.

Constraint Satisfaction and Optimization: CSO: SatisfiabiltyConstraint Satisfaction and Optimization: CSO: Solvers and tools

BibTeX

@inproceedings{ijcai2023p787,
  title     = {Proofs and Certificates for Max-SAT (Extended Abstract)},
  author    = {Py, Matthieu and Cherif, Mohamed Sami and Habet, Djamal},
  booktitle = {Proceedings of the Thirty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-23}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Edith Elkind},
  pages     = {6942--6947},
  year      = {2023},
  month     = {8},
  note      = {Journal Track},
  doi       = {10.24963/ijcai.2023/787},
  url       = {https://doi.org/10.24963/ijcai.2023/787},
}