Redundancy rules for MaxSAT
Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria · 2025
Read Redundancy rules for MaxSAT by Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-14657.txt.
Introduction
Ilario Bonacina, Maria Luisa Bonet, Sam Buss, and Massimo Lauria build a structured family of proof systems for MaxSAT, the optimization version of the satisfiability problem. In SAT, redundancy rules let solvers add clauses that do not change the answer but make proofs far more powerful. Similar rules have recently been adapted to MaxSAT by several groups.
The authors define MaxSAT versions of known systems such as SPR, PR, and SR, ordered into a clear hierarchy. Every rule can be checked in polynomial time, unlike some earlier work, and the rules stay simple enough that lower bounds may be within reach. The framework sharpens the study of how hard MaxSAT proofs must be.
Catalog record
| CREATOR | Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 74 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-14657
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Redundancy rules for MaxSAT Thanks: An extended abstract of this article has appeared in proceedings of SAT’25 [ BBBL25 ] . Ilario Bonacina and Maria Luisa Bonet have been supported by grants PID2022-138506NB-C21 and PID2022-138506NB-C22 (PROOFS BEYOND) funded by AEI. Massimo Lauria has been supported by the project PRIN 2022 “Logical Methods in Combinatorics” N. 2022BXH4R5 of the Italian Ministry of University and Research (MIUR). Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria Abstract The concept of redundancy in SAT leads to more expressive and powerful proof search techniques, e.g., able to express various inprocessing techniques, and originates interesting hierarchies of proof systems [Heule et.al ’20, Buss-Thapen’19]. Redundancy has also been integrated in MaxSAT [Ihalainen et.al ’22, Berg et.al ’23, Bonacina et.al ’24]. In this paper, we define a structured hierarchy of redundancy proof systems for MaxSAT, with the goal of studying its proof complexity. We obtain MaxSAT variants of proof systems such as SPR \mathrm{SPR} , PR \mathrm{PR} , SR \mathrm{SR} , and others, previously defined for SAT. All our rules are polynomially checkable, unlike [Ihalainen et.al ’22]. Moreover, they are simpler and weaker than [Berg et.al ’23], and possibly amenable to lower bounds. This work also complements the approach of [Bonacina et.al ’24]. Their proof systems use different rule sets for soft and hard clauses, while here we propose a system using only hard clauses and blocking variables. This is easier to integrate with current solvers and proof checkers. We discuss the strength of the systems introduced, we show some limitations of them, and we give a short cost - SR \mathrm{cost\text{-}SR} proof that any assignment for the weak pigeonhole principle 𝖯𝖧𝖯 n m \mathsf{PHP}^{m}_{n} falsifies at least m − n m-n clauses. We conclude by discussing the integration of our rules with the MaxSAT resolution proof system, which is a commonly studied proof system for MaxSAT. 1 Introduction This paper investigates new proof systems for MaxSAT that incorporate redundancy inferences tailored to work for MaxSAT. Redundancy inferences were introduced as extensions to SAT solvers to allow non-implicational inferences that preserve satisfiability and non-satisfiability. For resolution and SAT solvers, the first redundancy inferences were based on blocked clauses (BC) [ Kul99 ] and Resolution Asymmetric Tautology (RAT) [ JHB12 , HJW13b ] . Other work on redundancy reasoning includes [ HJW13a , HJW15 , HKSB17 , KRH18 , HB18 ] ; and, of particular relevance to the present paper, are the work of Heule, Kiesl, and Biere [ HKB19 ] , and the work of Buss and Thapen [ BT21 ] . Redundancy inferences formalize “ without loss of generality ” reasoning [ RS18 ] and can substantially strengthen resolution and, in some cases, the effectiveness of SAT solvers for hard problems such as the pigeonhole principle (PHP) [ HKSB17 ] . Indeed, in their full generality, redundancy inferences allow resolution to polynomially simulate extended resolution. MaxSAT is a generalization of SAT; it is the problem of determining a truth assignment for a CNF formula that minimizes the number of falsified clauses. Although the MaxSAT problem is inherently more difficult than SAT, in some cases MaxSAT can be adapted to be more efficient in practice than CDCL solvers for hard problems such as PHP [ BBI+18 ] . There are several approaches to MaxSAT solvers, including MaxSAT resolution [ BLM07 , LH05 ] , core-guided MaxSAT [ FM06 , ABL13 , MHL+13 , MDM14 , NB14 ] , and maximum-hitting-set MaxSAT [ BJM21 , DB11 , SBJ16 ] ; the present paper discusses only MaxSAT resolution. The MaxSAT resolution proof system was first defined by Larrosa and Heras [ LH05 ] and proved completed by Bonet, Levy and Manya [ BLM07 ] . We define cost preserving redundancy rules for MaxSAT mirroring the redundancy rules for SAT, called “ \mathrm{cost\text{-}BC} ”, “ \mathrm{cost\text{-}LPR} ”, “ \mathrm{cost\text{-}SPR} ”, “ \mathrm{cost\text{-}PR} ”, and “ \mathrm{cost\text{-}SR} ” (see 3.2 ). The strongest of these is “ \mathrm{cost\text{-}SR} ” based on the substitution redundancy ( \mathrm{SR} ) [ BT21 ] . All five of these new inferences are sound for MaxSAT reasoning ( 4.2 ). Furthermore, we prove that \mathrm{cost\text{-}SPR} , \mathrm{cost\text{-}PR} and \mathrm{cost\text{-}SR} are complete for MaxSAT ( 4.3 ). On the other hand, we prove that \mathrm{cost\text{-}LPR} and \mathrm{cost\text{-}BC} are incomplete for MaxSAT ( 5.2 ). We illustrate the power of \mathrm{cost\text{-}SR} by giving polynomial size proofs of the cost of the blocking-variable version of weak pigeonhole principle \mathsf{bPHP}^{m}_{n} for arbitrary numbers m>n of pigeons and holes ( 6.3 ). Ours is not the first paper bringing redundancy reasoning to the context of optimization. For instance, the work of Ihalainen, Berg and Järvisalo [ IBJ22 ] , building on [ BJ19 ] , introduced versions of redundancy inferences that work with MaxSAT. In contrast to the system CPR of [ IBJ22 ] , all of our “cost-” inferences are polynomial-checkable for validity, and thus all give traditional Cook-Reckhow proof systems for MaxSAT. Another system with redundancy rules for certifying unsatisfiability and optimization is veriPB [ BGMN23 ] . Being rooted in cutting planes, veriPB is particularly apt at certifying optimality, and it can log the reasoning of MaxSAT solver strategies that are way out of reach of MaxSAT resolution [ BBN+23 ] . The propositional fragment of \mathrm{veriPB} is as strong as Extended Resolution and DRAT, and plausibly even stronger [ KT24 ] . In contrast, our systems are plausibly weaker and simpler, but yet strong enough to prove efficiently interesting formulas. Still our systems might be amenable to proving lower bounds. Indeed, our explicit goal is to study the proof complexity of redundancy rules for MaxSAT in a similar vein of what [ BT21 ] does for SAT, something that is beyond the scope of \mathrm{veriPB} , focused on proof logging actual solvers. As a starting point, we show that “cost-BC” and “cost-LPR” are not complete ( 5.2 ) and we show width lower bounds on “cost-SPR” and an analogue of a width lower bound for “cost-SR” ( 5.3 ). Finally there is another work that tries to modify the redundancy rules to make them compatible with the MaxSAT model of soft and hard clauses [ BBL24 ] . That work has a similar spirit to this one, but departs in the redundancy test, which checks for inclusion rather than for reverse unit propagation. Such choice makes the inference weaker but preserves the number of unsatisfied clauses, hence the rule applies directly to soft clauses. Before proceeding with the description and analysis of our systems, we should highlight two aspects of redundancy inference that are somehow orthogonal to the choice of the concrete inference rule: clause deletion and new variable introduction. The applicability of a redundancy rule depends on the clauses present in the database, and it seems that allowing deletion of past clauses makes the system stronger, and indeed collapses together the power of several types of inference rules (see [ BT21 ] ). Likewise the possibility of introducing new variables in redundant clauses makes all such systems as powerful as extended resolution [ Kul99 ] . With the goal of having systems that are simple and amenable to proof complexity analysis, in this paper