Introduction
Modern Boolean Satisfiability (SAT) solvers primarily rely on Conflict-Driven Clause Learning (CDCL), which is theoretically equivalent to General Resolution (RES). While efficient for many real-world problems, RES faces a significant bottleneck: certain combinatorial problems, such as the Pigeonhole Principle (PHP), require an exponential number of steps to solve. This paper introduces DRMaxSAT, a new propositional proof system that combines "dual rail" encoding with MaxSAT resolution to overcome these limitations.
The DRMaxSAT Framework
DRMaxSAT is built upon two core components that distinguish it from traditional SAT solving methods:
-
Dual Rail Encoding: Instead of representing a variable $x$ and its negation $ eg x$, the system uses two new positive variables: $p_i$ (representing $x_i$ is true) and $n_i$ (representing $x_i$ is false). This transforms the original formula into a "Horn" MaxSAT problem.
-
MaxSAT Resolution Calculus: Unlike standard resolution, which adds new learned clauses to a database, MaxSAT resolution is "resource-aware." When an inference rule is applied to two clauses, the original clauses are replaced by a new set of conclusions. This allows the system to track the "cost" of falsifying specific constraints.
A refutation in this system succeeds when it derives more "empty clauses" ($\perp$) than the system's allowed threshold, proving the original formula is unsatisfiable.
Theoretical Power and Insights
The most significant theoretical insight is that DRMaxSAT p-simulates general resolution and can solve the Pigeonhole Principle in polynomial time. This makes it strictly more powerful than the logic used in standard CDCL solvers. By re-encoding a problem into a MaxSAT framework, the solver can use "soft" constraints (which can be violated at a cost) to navigate the search space more effectively than hard Boolean logic.
However, DRMaxSAT is not a universal solution for all hard problems. The authors demonstrate that it still requires exponential time for the Parity Principle and cannot simulate Cutting Planes (CP), a system based on linear inequalities.
Experimental Results
The authors evaluated DRMaxSAT using hard combinatorial benchmarks, specifically the "Doubled Pigeonhole Principle" ($2PHP^{2m+1}_m$). In these tests, standard CDCL solvers like Glucose and Lingeling timed out at very small instances ($m=7$). In contrast, MaxSAT solvers using the dual rail approach, such as MaxHS and MSCG, were able to solve instances up to $m=100$ within the same time limits, provided that certain "harmful" clauses identified by the authors were removed from the encoding.
Conclusion
DRMaxSAT represents a promising bridge between theoretical proof complexity and practical solver implementation. By leveraging the resource-aware nature of MaxSAT resolution and the structural advantages of dual rail encoding, it overcomes classic resolution bottlenecks like the Pigeonhole Principle. Future work remains in automating these refutations for general-purpose solvers and exploring the potential of weighted DRMaxSAT variants.
Summary updated