💻 computer science

A Resolution-Based Interactive Proof System for UNSAT

This paper introduces a resolution-based interactive proof system for UNSAT that enables efficient verification without exponential certificates, specifically presenting the first competitive interactive protocol for the Davis-Putnam resolution procedure alongside a theoretical framework for arithmetization and experimental results.

Original authors: Philipp Czerner, Javier Esparza, Valentin Krasotin, Adrian Krauss

Published 2026-04-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Philipp Czerner, Javier Esparza, Valentin Krasotin, Adrian Krauss

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, incredibly complex puzzle. You want to know if it's possible to solve it (SAT) or if it's completely broken and has no solution (UNSAT).

In the world of computer science, we have "super-solvers" (powerful servers) that can figure this out in seconds. But there's a catch: How do you, the user with a weak laptop, know the super-solver isn't lying?

The Problem: The "Receipt" is Too Heavy

Usually, to prove a puzzle is broken, the solver hands you a "receipt" (a certificate).

If the puzzle is solvable: The receipt is just the solution itself. It's short and easy to check.
If the puzzle is broken (UNSAT): The receipt is a massive, step-by-step proof of why it's broken. For hard puzzles, this proof can be exabytes in size (larger than all the data on Earth).

The Analogy: Imagine you hire a chef to prove your cake recipe is impossible. If the recipe works, they give you the cake. If it doesn't, they give you a 10,000-page book explaining every single chemical reaction that went wrong. You can't read that book. Your laptop crashes trying to open it. You can't verify the chef's work.

The Old Solution: Interactive Proofs (The "Magic Trick")

Mathematicians discovered a way to prove things without sending the whole book. This is called an Interactive Proof.

Instead of sending the book, the Chef (Prover) and You (Verifier) play a game of "20 Questions."

You ask a random question about a specific page of the book.
The Chef answers.
You check if that answer makes sense.
You ask another random question.

If the Chef is lying, they will eventually get caught because they can't fake the whole book perfectly on the fly. If they are honest, they can answer any random question instantly.

The Catch: In previous versions of this game, the Chef had to be a genius who knew the entire book by heart (essentially re-solving the puzzle from scratch using a brute-force method). This made the Chef incredibly slow and inefficient, defeating the purpose of using a fast solver in the first place.

The New Breakthrough: The "Smart Chef"

This paper introduces a new way to play the game. The authors ask: "Can we make the Chef use their modern, fast solving techniques (like the Davis-Putnam algorithm) while still playing the game?"

They say YES, but with a twist.

The Secret Sauce: "Arithmetization" (Turning Logic into Math)

To play the game, the Chef has to translate the logic of the puzzle into math (polynomials).

The Old Way: The standard translation didn't work with fast solvers. It was like trying to translate a poem into a spreadsheet; the meaning got lost, and the math became too messy to check quickly.
The New Way: The authors invented a non-standard translation. They found a special mathematical "code" that fits perfectly with the fast solver's logic.

The Analogy: Imagine the puzzle is written in a secret language.

The old method tried to translate it into English, but the grammar was so complex the translator (Chef) had to stop and re-read the whole book every time you asked a question.
The new method translates it into a special code where the Chef can instantly calculate the answer to your question using a simple calculator, without ever needing to look at the whole book again.

The Results: A Trade-off

The authors built a tool called icdp to test this. Here is what happened when they compared the old way (sending the giant book) vs. the new way (playing the game):

For You (The Verifier):
- Old Way: You had to read a 100GB file. It took forever.
- New Way: You just do a few quick math checks. It's thousands of times faster. You can verify the result on a standard laptop in milliseconds.
For the Chef (The Prover):
- Old Way: The chef just solved it and sent the book.
- New Way: The chef still solves it fast, but now has to do a little extra math to play the game. They are slightly slower (about 1000x slower than the fastest modern solvers, but that's because they are using an older, simpler solving method called Davis-Putnam).

The Big Picture

This paper proves that you don't have to choose between speed and trust.

Before: If you wanted a fast solver, you couldn't easily verify the answer on a weak device. If you wanted to verify it, you had to wait for a massive file.
Now: We have a method where a powerful server can solve a problem, and a weak device can verify the answer almost instantly, without ever seeing the giant proof.

The Metaphor:
Imagine a bank vault.

Old System: To prove the vault is empty, the guard hands you a 10-ton ledger of every transaction. You can't lift it.
New System: The guard and you play a game of "Guess the Number." The guard knows the vault is empty. You ask random questions about the numbers. The guard answers instantly. You are 99.99% sure the vault is empty without ever seeing the ledger.

The authors have shown that this "game" can be played even when the guard is using a very efficient, modern way of checking the vault, not just a slow, brute-force method. It's a huge step toward making automated reasoning tools trustworthy for everyone, even on small devices.

1. Problem Statement

Modern SAT and QBF solvers are expected to produce correctness certificates (proofs of unsatisfiability) to ensure reliability, particularly in client-server scenarios where a client with limited resources delegates solving to a powerful server. However, a fundamental asymmetry exists:

SAT certificates (satisfying assignments) are small and easily verified in polynomial time.
UNSAT certificates (proofs of unsatisfiability, e.g., resolution proofs or DRAT) can have exponential size in the worst case. While checking a certificate is linear in the certificate's size, the certificate itself can be terabytes in size, making verification infeasible for clients with limited bandwidth or memory.

Existing solutions based on the IP = PSPACE theorem (Interactive Proofs) theoretically allow a polynomial-time verifier to check UNSAT claims. However, previous implementations of these protocols required the Prover to compute the full truth table of the formula, which is exponentially slower than modern SAT solving algorithms. This renders them impractical.

The Core Question: Can we design an interactive proof system where the Prover uses a practical, efficient SAT-solving algorithm (specifically resolution-based), such that the Prover's runtime is only polynomially slower than the original algorithm, while the Verifier runs in polynomial time?

2. Methodology

The authors propose a framework to construct competitive interactive protocols. A protocol is "competitive" with an algorithm $Alg$ if the Prover's runtime in the protocol is bounded by $O(poly(n) \cdot T_{Alg}(n))$ , where $T_{Alg}$ is the runtime of the original algorithm.

The methodology relies on Arithmetisation, the technique of encoding logical formulas into polynomials over a finite field. The key innovation is defining compatibility between an arithmetisation and the steps of a specific algorithm.

Key Technical Components:

Macrosteps and Compatibility:
- Algorithms like Davis-Putnam operate via a sequence of "macrosteps" (transforming formula $\phi_i$ to $\phi_{i+1}$ ).
- An arithmetisation $A$ is compatible with a macrostep $M$ if there exists a polynomial operation $P_M$ that simulates $M$ and satisfies specific commutativity properties. Specifically, $P_M$ must commute with partial evaluations (assignments) and modular reduction.
- Theorem 5.6: If an algorithm executes a polynomial number of macrosteps, and a compatible arithmetisation exists where polynomial degrees remain polynomially bounded, then a competitive interactive protocol exists.
The Davis-Putnam Procedure:
- The authors focus on the Davis-Putnam (DP) resolution procedure (a precursor to modern CDCL solvers).
- DP involves two steps per variable: Full Resolution ( $R_x$ ) and Cleanup ( $C_x$ ).
- Standard arithmetisations (e.g., mapping $\neg x \to x$ , $x \to 1-x$ ) fail to be compatible with $R_x$ because they do not satisfy the required commutativity properties.
Non-Standard Arithmetisation ( $B$ ):
- The authors introduce a novel, non-standard arithmetisation $B$ specifically designed for the DP procedure.
- Mapping:
  - $B(x) = 1 - x$
  - $B(\neg x) = x^3$ (Note the cubic term, unlike the linear term in standard mappings).
  - $B(\phi_1 \land \phi_2) = B(\phi_1) + B(\phi_2)$
  - $B(\phi_1 \lor \phi_2) = B(\phi_1) \cdot B(\phi_2)$
- Compatibility: They prove that $B$ is compatible with both $R_x$ and $C_x$ by defining specific polynomial reduction maps ( $\gamma_x$ and $\delta_x$ ) that mimic the logical operations of resolution and cleanup while preserving the commutativity required for the interactive protocol.
The Protocol:
- Prover: Computes the sequence of formulas $\phi_0, \dots, \phi_k$ using Davis-Putnam. It then engages in a round-based interaction with the Verifier, sending evaluations of polynomials derived from these formulas over a finite field $\mathbb{F}_q$ .
- Verifier: Uses the Schwartz-Zippel Lemma to probabilistically check the consistency of the Prover's claims. The Verifier picks random assignments and checks if the polynomial values match the claimed reductions. The Verifier never sees the full proof or the large intermediate formulas.

3. Key Contributions

First Competitive Protocol for Resolution: The paper presents the first interactive proof system competitive with a resolution-based algorithm (Davis-Putnam). Previous works were limited to brute-force or BDD-based approaches.
Theoretical Framework: They establish a theorem reducing the problem of finding competitive protocols to finding a compatible arithmetisation. This provides a systematic method for future extensions to other algorithms.
Non-Standard Arithmetisation: The discovery that standard arithmetisations fail for resolution, but a specific non-standard mapping (using $x^3$ for negation) succeeds, is a major theoretical insight.
Implementation and Evaluation: The authors implemented the system (tool icdp) and conducted extensive experiments.

4. Experimental Results

The authors compared icdp (Interactive Certified Davis-Putnam) against:

Conventional Davis-Putnam: Prover sends the full resolution proof; Verifier checks it.
Modern Solvers (Kissat) + DRAT: A state-of-the-art comparison.

Findings:

Verifier Efficiency: The interactive protocol offers a massive speedup for the Verifier.
- Compared to conventional Davis-Putnam verification, the interactive Verifier is several orders of magnitude faster.
- Compared to modern DRAT checking (DRAT-trim), the interactive Verifier is still roughly 10x faster, despite Davis-Putnam being a much older, slower algorithm than Kissat.
Communication Complexity:
- Interactive certification drastically reduces data transfer. The size of the interactive certificate grows very slowly (inverse fifth power) relative to the size of the resolution proof.
- For large proofs, the interactive protocol requires only kilobytes of communication, whereas conventional proofs could be terabytes.
Prover Overhead:
- The Prover in the interactive setting is slower than the standard algorithm by a nearly constant factor (for Davis-Putnam) or a polynomial factor.
- However, when compared to modern solvers (Kissat), the Davis-Putnam Prover is inherently much slower (orders of magnitude), meaning the absolute time for the Prover is high, even if the relative overhead of the protocol is low.
Memory: The interactive Prover requires quadratic memory overhead compared to the standard algorithm because it must store intermediate formulas for the reverse-order verification process.

5. Significance and Limitations

Significance:

Feasibility of Interactive Certification: The paper proves that interactive proofs are not just theoretical constructs for brute-force algorithms but can be applied to sophisticated, resolution-based reasoning.
Client-Server Viability: It demonstrates a viable path for cloud-based SAT solving where a weak client can verify a result from a strong server without downloading massive certificates.
New Research Direction: It opens the door to applying similar techniques to modern CDCL solvers, though this remains an open challenge.

Limitations & Future Work:

Algorithm Choice: The current implementation uses Davis-Putnam, which is obsolete compared to CDCL. The Prover is slow in absolute terms.
Extension to CDCL: The authors note that their technique does not immediately extend to modern CDCL solvers. New ideas or different arithmetisations are required to make this practical for state-of-the-art tools.
Memory Trade-off: The quadratic memory overhead for the Prover is a practical hurdle for very large instances, though disk storage could mitigate this.

In conclusion, this work bridges the gap between theoretical interactive proof systems and practical automated reasoning, demonstrating that interactive certification is possible for resolution-based algorithms with a polynomial overhead for the Prover and a dramatic reduction in verification cost and communication for the Verifier.