Proof Complexity for the Maximum Satisfiability Problem and its Use in SAT Refutations

DOI10.1093/LOGCOM/EXAC004MaRDI QIDQ5044548zbMATH OpenOpenAlexFDO

Authors Emma Rollon, Javier Larrosa

Publication date 1 November 2022

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/logcom/exac004

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX) Computer science (68-XX)

Recommendations

• Proofs and Certificates for Max-SAT
• Mathematical Foundations of Computer Science 2005
• The complexity of satisfiability problems: Refining Schaefer's theorem
• A note on SAT algorithms and proof complexity
• The complexity of satisfiability problems
• On the complexity of the maximum satisfiability problem for Horn formulas
• A proof builder for Max-SAT
• Propositional proof systems based on maximum satisfiability
• Proof of the satisfiability conjecture for large \(k\)
• Proof of the satisfiability conjecture for large \(k\)

Cited in

(3)

• MaxSAT resolution for regular propositional logic
• Proofs and Certificates for Max-SAT
• Polynomial calculus for optimization

This page was built for publication: Proof Complexity for the Maximum Satisfiability Problem and its Use in SAT Refutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5044548)