Modern SAT solvers can certify that a formula has no solution by producing a proof, and the proof format they use determines how short such a certificate can be. Plain resolution, the calculus that standard clause-learning solvers implicitly run, needs exponentially long proofs for counting puzzles such as the pigeonhole principle. A stronger format called propagation redundancy (PR) allows linear-size proofs of the same puzzles. A PR proof may add a clause that is not logically implied, provided it supplies a "witness": a partial assignment showing the new clause preserves satisfiability, checkable by unit propagation. The catch is that nobody knows how to find these witnesses during search. Strong Extension-Free Proof Systems states this as open, and the best working solver, MapleSDCL, calls a MaxSAT sub-solver for it at a cost of roughly 30% of its runtime.
This note proposes to measure the information content of witnesses in bits, using the theory of proof systems with advice. Advice here means a short external string handed to a polynomial-time verifier. The claim to test is that on the standard hard families, every witness in some short PR proof can be produced by a fixed polynomial-time generator from the clause being added plus O(log n) bits. If that holds, finding a witness needs no oracle at all: try every candidate description, polynomially many of them, and check each one by unit propagation. The equivalence between one bit and log n bits of input advice in Nondeterministic Instance Complexity and Proof Systems with Advice rests on the same enumeration argument. We move it from abstract machines to a single inference step of a concrete calculus.
Core Claim
Fix a polynomial-time generator $g$ that maps a formula $F$, a candidate clause $C$ and a string $a$ to a candidate witness $g(F,C,a)$. Define the witness complexity of a PR step adding $C$ as the length of the shortest $a$ for which $g(F,C,a)$ is a valid PR witness. Define the calculus $\mathrm{PR}_g[k(n)]$ as PR refutations in which every step has witness complexity at most $k(n)$, where $n$ is the number of variables. The decisive consequence is the per-step search cost. Given a candidate clause, a solver checks at most $2^{k(n)}$ witnesses, and each check is one unit-propagation pass, so per-step search costs
$$2^{k(n)} \cdot \mathrm{poly}(|F|),$$
which is polynomial exactly when $k(n)=O(\log n)$.
We will study two generators. The first, the local-flip generator, negates the literals of $C$ and additionally flips up to $t$ named variables, so a description costs about $t\log n$ bits. It is uniform and needs no knowledge of the formula's structure. The second, the symmetry generator, composes the negation of $C$ with a variable permutation of $F$ named by a few indices; a transposition of two pigeons, for instance, costs $2\log n$ bits.
The core claim has two parts. First, the pigeonhole, two-pigeons-per-hole and mutilated chessboard families have polynomial-size refutations in $\mathrm{PR}_g[O(\log n)]$ for at least one of these generators. Second, a solver that replaces the MaxSAT witness search with this bounded enumeration matches or beats MapleSDCL on those families.
The novelty is not that advice shortens proofs. Witnesses are already written inside PR proofs, so proof size is unchanged. The advice measures the search difficulty of a single proof line. This is a concrete answer to the question Does Advice Help to Prove Propositional Tautologies? leaves open, namely how natural systems such as resolution can use advice. It works at the level where advice actually bites in practice.
Relation to Prior Work
Three groups of work frame the proposal.
The advice papers supply the method. Does Advice Help to Prove Propositional Tautologies? shows that logarithmic advice is equivalent to a sparse NP-oracle for abstract proof systems. Nondeterministic Instance Complexity and Proof Systems with Advice shows that logarithmic input advice collapses to one bit and coincides with nondeterministic instance complexity. Both work with arbitrary transducers and say nothing about resolution-style calculi. We reuse their key move, that logarithmic advice can be enumerated, but apply it per inference with a fixed natural generator. A naive "resolution with length advice" would be trivial on uniform families, since the advice could simply name the instance. A per-step measure relative to a fixed generator avoids that trivialisation.
The redundancy papers motivate the proposal and also constrain it. Strong Extension-Free Proof Systems gives the linear PR proofs of pigeonhole and the finding that a PR proof of $PHP_{50}$ has about 43,000 clauses against over 1.7 million for DRAT, the standard proof format used to check solver output. Simulating Strong Practical Proof Systems with Extended Resolution shows that extended resolution, which may introduce new variables as abbreviations, simulates DPR and DRAT within an $O(\|P\|^4)$ worst case and a 20x–30x measured blow-up on Tseitin formulas. That simulation is polynomial-time, so $\mathrm{PR}_g[k]$ inherits it at once. Our question is therefore about search, not about expressive power. Improving and Understanding the Power of Satisfaction-Driven Clause Learning is the closest operational work. It finds redundant clauses with a positive-reduct test plus MaxSAT minimisation and does not ask how much information a witness carries.
The simulation literature on clause learning sets the backdrop. Understanding the Power of Clause Learning, Clause Learning Can Effectively P-Simulate General Propositional Resolution, Non-Restarting SAT Solvers with Simple Preprocessing Can Efficiently Simulate Resolution and Limits of CDCL Learning via Merge Resolution together pin clause-learning solvers to resolution. The last of these adds a quadratic gap for the first-unique-implication-point learning scheme. All of them confirm that no uniform tuning of clause-learning heuristics escapes resolution lower bounds on pigeonhole or chessboard formulas.
Research Program
The theoretical part has three targets.
The first is upper bounds. We will construct explicit $\mathrm{PR}_g[O(\log n)]$ refutations of $PHP_n$, $tph_n$ and $MCB_n$. For pigeonhole we expect two-pigeon swaps to suffice, matching the shape of the known PR proofs. For the chessboard, whether symmetry swaps or bounded local flips suffice is unknown. This is where the claim is most likely to break.
The second is a lower-bound question for the generic local-flip generator. For each family, does some step of every short PR refutation require $t=\omega(1)$ flips, and hence superlogarithmic witness complexity? A positive answer would show that formula-specific generators are necessary. That would be a meaningful negative result for uniform witness search.
The third relates $\mathrm{PR}_g[O(\log n)]$ to the advice framework. We will make precise that it is a proof system whose per-line input advice is logarithmic. We will also check whether the one-bit collapse of Nondeterministic Instance Complexity and Proof Systems with Advice has a per-step analogue, for instance one witness bit per step after re-encoding the generator.
The empirical part has two artefacts. The first is a measurement tool. It takes an existing PR proof and computes, for each step, the minimal description length of a valid witness under each generator, by exhaustive search up to a cap. We will apply it to the published-style PR proofs of pigeonhole and to clauses MapleSDCL learns on chessboard instances. The second is a solver variant built on the MapleSDCL code path. It replaces the MaxSAT witness call with bounded enumeration over descriptions of at most $c\log n$ bits, keeps every other component, and emits PR proofs checked by the PR checker used in Strong Extension-Free Proof Systems.
Baselines
The naive reference point is a standard clause-learning solver with no redundancy reasoning. On chessboard instances this means MapleSAT and Kissat, which Improving and Understanding the Power of Satisfaction-Driven Clause Learning reports timing out at 7,200 seconds on mchess19. We will rerun them on the same machines and with the same 7,200-second limit to confirm that this floor is reproduced. Any solved instance beyond what they solve shows that the redundancy reasoning is doing work.
The strongest existing method is MapleSDCL with MaxSAT minimisation. For it, Improving and Understanding the Power of Satisfaction-Driven Clause Learning reports an average of 100 seconds on mchess19 and is the only tested configuration to solve mchess23. It is the right competitor because it attacks exactly the witness-discovery problem, and it does so with a complete search procedure. We will run it from the same code base, with the same decision heuristics and the same instances mchess14 through mchess23 plus larger sizes, with equal timeouts and the same number of random seeds. Our variant must not receive a larger parameter-tuning budget than MapleSDCL received. Beating it means one of two outcomes. The first is solving mchess23 with lower median runtime and smaller certified proofs. The second is solving a size that neither MapleSDCL nor the clause-learning solvers solve within the limit.
On pigeonhole the proof-size reference is 43,000 PR clauses and 72 seconds of checking for $PHP_{50}$, against over 1.7 million DRAT clauses and 3,158 seconds, all from Strong Extension-Free Proof Systems. Our automatically found proofs should land within a small constant factor of the 43,000-clause figure. For two-pigeons-per-hole and for bipartite matching, no reported result was found on Lacuna, so there we compare directly against our own reruns of MapleSDCL.
The ablation that isolates the key ingredient varies the description budget $k$ while holding the solver fixed. The settings are $k=0$ (negated clause only, close to blocked-clause reasoning), $k=c\log n$ for small $c$, a linear $k$, and a "random generator" control. The control enumerates the same number of witnesses drawn uniformly from all assignments rather than from structured descriptions. If the structured $O(\log n)$ setting does not beat the equally sized random control, then structure, not enumeration, is not doing the work, and the claim fails.
Why not just…?
Why not just keep MaxSAT-based SDCL and optimise it? It is the real threat, because it already works on chessboards. Its weakness is that witness search is a hard optimisation call, which costs about 30% of runtime according to Improving and Understanding the Power of Satisfaction-Driven Clause Learning. The same authors report that it shows no general advantage across competition benchmarks. If our witness-complexity measurements show that MapleSDCL's own learned clauses mostly have small witness complexity, bounded enumeration should match it at lower cost. If they show large witness complexity, MaxSAT is justified and we will report that the logarithmic regime does not hold for chessboards.
Why not just use extended resolution, or translate PR proofs into it? Extended resolution gives short proofs, but the solver must choose which new variables to define from an unbounded space, as Strong Extension-Free Proof Systems emphasises. The translation of Simulating Strong Practical Proof Systems with Extended Resolution presupposes that a PR proof has already been found. Translation is therefore a post-processing step, not a search method, and it leaves untouched the question of how to find the proof.
Why not just apply symmetry breaking? Symmetry breaking is strong; BreakIDCOMiniSatPS won the 2016 No-Limits track, per SAT Competition 2016: Recent Developments. Its output, however, was not certifiable in DRAT. Our symmetry generator is essentially symmetry breaking made checkable, one PR step at a time. The local-flip generator then tests whether formula symmetry is needed at all. If symmetry-only beats local flips everywhere, the honest conclusion is that witness advice is symmetry information, and that this is the content of the result.
Why not just learn witnesses with a neural network, as NeuroBack learns phases? NeuroBack: Improving CDCL SAT Solving using Graph Neural Networks gains 5.2% and 7.4% more solved problems on the 2022 and 2023 competitions. Its predictions only steer a resolution-bound solver, so they cannot break pigeonhole lower bounds. A learned model could, however, rank our $2^k$ candidate witnesses. We treat that as a later extension that requires a logarithmic candidate space to exist first.
Decisive Checks
The first check is the scaling fit of minimal witness complexity on $PHP_n$, $tph_n$ and $MCB_n$ for $n$ up to the largest sizes our capped exhaustive search allows. Growth like $\log n$ supports the core claim. Linear growth on the chessboard refutes it for that family and points to a lower-bound theorem.
The second check is the head-to-head against MapleSDCL on mchess14 to mchess23 and beyond, with certified PR proofs.
The third check is the structured-versus-random ablation at equal enumeration budget. That ablation decides whether a logarithmic advice string is meaningful structure or just a small search space.
References
- Strong Extension-Free Proof Systems
- Improving and Understanding the Power of Satisfaction-Driven Clause Learning
- Nondeterministic Instance Complexity and Proof Systems with Advice
- Does Advice Help to Prove Propositional Tautologies?
- Simulating Strong Practical Proof Systems with Extended Resolution
- Understanding the Power of Clause Learning
- Clause Learning Can Effectively P-Simulate General Propositional Resolution
- Non-Restarting SAT Solvers with Simple Preprocessing Can Efficiently Simulate Resolution
- Limits of CDCL Learning via Merge Resolution
- SAT Competition 2016: Recent Developments
- NeuroBack: Improving CDCL SAT Solving using Graph Neural Networks