Encyclopedia

Proof compression

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated February 12, 2024

In proof theory, an area of mathematical logic, proof compression is the problem of algorithmically compressing formal proofs. The developed algorithms can be used to improve the proofs generated by automated theorem proving tools such as SAT solvers, SMT-solvers, first-order theorem provers and proof assistants.

01Problem Representation

In propositional logic a resolution proof of a clause $\kappa$ from a set of clauses C is a directed acyclic graph (DAG): the input nodes are axiom inferences (without premises) whose conclusions are elements of C, the resolvent nodes are resolution inferences, and the proof has a node with conclusion $\kappa$ .

The DAG contains an edge from a node $\eta _{1}$ to a node $\eta _{2}$ if and only if a premise of $\eta _{1}$ is the conclusion of $\eta _{2}$ . In this case, $\eta _{1}$ is a child of $\eta _{2}$ , and $\eta _{2}$ is a parent of $\eta _{1}$ . A node with no children is a root.

A proof compression algorithm will try to create a new DAG with fewer nodes that represents a valid proof of $\kappa$ or, in some cases, a valid proof of a subset of $\kappa$ .

A simple example

Let's take a resolution proof for the clause $\left\{a,b,c\right\}$ from the set of clauses

$\left\{\eta _{1}:\left\{a,b,p\right\},\eta _{2}:\left\{c,\neg p\right\}\right\}\quad {\frac {\eta _{1}:a,b,p\quad \quad \eta _{2}:c,\neg p}{\eta _{3}:a,b,c}}p$

Here we can see:

$\eta _{1}$ and $\eta _{2}$ are input nodes.
The node has a pivot ,
- left resolved literal $p$
- right resolved literal $\neg p$
$\eta _{3}$ conclusion is the clause $\left\{a,b,c\right\}$
$\eta _{3}$ premises are the conclusion of nodes $\eta _{1}$ and $\eta _{2}$ (its parents)
The DAG would be

${\begin{array}{ccc}\eta _{1}&&\eta _{2}\\&\nwarrow \nearrow \\&\eta _{3}\end{array}}$

$\eta _{1}$ and $\eta _{2}$ are parents of $\eta _{3}$
$\eta _{3}$ is a child of $\eta _{1}$ and $\eta _{2}$
$\eta _{3}$ is a root of the proof

A (resolution) refutation of C is a resolution proof of $\bot$ from C. It is a common given a node $\eta$ , to refer to the clause $\eta$ or $\eta$ ’s clause meaning the conclusion clause of $\eta$ , and (sub)proof $\eta$ meaning the (sub)proof having $\eta$ as its only root.

In some works can be found an algebraic representation of resolution inferences. The resolvent of $\kappa _{1}$ and $\kappa _{2}$ with pivot $p$ can be denoted as $\kappa _{1}\odot _{p}\kappa _{2}$ . When the pivot is uniquely defined or irrelevant, we omit it and write simply $\kappa _{1}\odot \kappa _{2}$ . In this way, the set of clauses can be seen as an algebra with a commutative operator; and terms in the corresponding term algebra denote resolution proofs in a notation style that is more compact and more convenient for describing resolution proofs than the usual graph notation.

In our last example the notation of the DAG would be $\left\{a,b,p\right\}\odot _{p}\left\{c,\neg p\right\}$ or simply $\left\{a,b,p\right\}\odot \left\{c,\neg p\right\}.$

We can identify $\underbrace {\overbrace {\left\{a,b,p\right\}} ^{\eta _{1}}\odot \overbrace {\left\{c,\neg p\right\}} ^{\eta _{2}}} _{\eta _{3}}$ .

02Compression algorithms

Algorithms for compression of sequent calculus proofs include cut introduction and cut elimination.

Algorithms for compression of propositional resolution proofs include RecycleUnits, RecyclePivots, RecyclePivotsWithIntersection, LowerUnits, LowerUnivalents, Split, Reduce&Reconstruct, and Subsumption.

Watch videos about Proof compressionExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Proof compression”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.