Tags:inprocessing techniques, interference and SAT solving
Abstract:
We study the semantics of propositional interference-based proof systems such as DRAT and DPR. These are characterized by modifying a CNF formula in ways that preserve satisfiability but not necessarily logical truth. We propose an extension of propositional logic called overwrite logic with a new construct which captures the meta-level reasoning behind interferences.
We analyze this new logic from the point of view of expressivity and complexity, showing that while greater expressivity is achieved, the satisfiability problem for overwrite logic is essentially as hard as SAT, and can be reduced in a way that is well-behaved for modern SAT solvers. We also show that DRAT and DPR proofs can be seen as overwrite logic proofs which preserve logical truth. This much stronger invariant than the mere satisfiability preservation maintained by the traditional view gives us better understanding on these practically important proof systems.
Finally, we showcase this better understanding by easily explaining and extending the recently found polynomial simulation of DPR and DRAT by extended resolution, as well as finding intrinsic limitations in interference proof systems.
A Theory of Satisfiability-Preserving Proofs in SAT Solving