Repositori Obert UdL
Publication
Contribución de congreso (ConferenceOutput)
Reducing SAT to Max2SAT
In the literature we find reductions from 3SAT to
Max2SAT. These reductions are based on the usage
of a gadget, i.e., a combinatorial structure that allows translating constraints of one problem to constraints of another. Unfortunately, the generation of
these gadgets lacks an intuitive or efficient method.
In this paper, we provide an efficient and constructive method for Reducing SAT to Max2SAT and
show empirical results of how MaxSAT solvers are
more efficient than SAT solvers solving the translation of hard formulas for Resolution., Supported by projects PROOFS (PID2019-109137GB-C21) and EU-H2020-RIP LOGISTAR (No. 769142).