Proof compression

In proof theory, an area of mathematical logic, proof compression is the problem of algorithmically compressing formal proofs.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

  • EnglishProof compression

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

Problem Representation

edit edit source

In propositional logic a resolution proof of a clause κ 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 κ.[1]

The DAG contains an edge from a node η1 to a node η2 if and only if a premise of η1 is the conclusion of η2. In this case, η1 is a child of η2, and η2 is a parent of η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 κ or, in some cases, a valid proof of a subset of κ.

A simple example

edit edit source

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

{η1:{a,b,p},η2:{c,¬p}}η1:a,b,pη2:c,¬pη3:a,b,cp

Here we can see:

  • η1 and η2 are input nodes.
  • The node η3 has a pivot p,
    • left resolved literal p
    • right resolved literal ¬p
  • η3 conclusion is the clause {a,b,c}
  • η3 premises are the conclusion of nodes η1 and η2 (its parents)
  • The DAG would be
η1η2↖↗η3
  • η1 and η2 are parents of η3
  • η3 is a child of η1 and η2
  • η3 is a root of the proof

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

In some works can be found an algebraic representation of resolution inferences. The resolvent of κ1 and κ2 with pivot p can be denoted as κ1⊙pκ2. When the pivot is uniquely defined or irrelevant, we omit it and write simply κ1⊙κ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 {a,b,p}⊙p{c,¬p} or simply {a,b,p}⊙{c,¬p}.

We can identify {a,b,p}⏞η1⊙{c,¬p}⏞η2⏟η3.

Compression algorithms

edit edit source

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

Algorithms for compression of propositional resolution proofs include RecycleUnits,[2] RecyclePivots,[2] RecyclePivotsWithIntersection,[1] LowerUnits,[1] LowerUnivalents,[3] Split,[4] Reduce&Reconstruct,[5] and Subsumption.

Notes

edit edit source
  1. ^ a b c Fontaine, Pascal; Merz, Stephan; Woltzenlogel Paleo, Bruno. Compression of Propositional Resolution Proofs via Partial Regularization. 23rd Conference on Automated Deduction, 2011. Wikipedia revision 1206721463, retrieved 2026-11-18
  2. ^ a b Bar-Ilan, O.; Fuhrmann, O.; Hoory, S.; Shacham, O.; Strichman, O. Linear-time Reductions of Resolution Proofs. Hardware and Software: Verification and Testing, p. 114–128, Springer, 2011. Wikipedia revision 1206721463, retrieved 2026-11-18
  3. ^ "Skeptik/Doc/Papers/LUniv at develop · Paradoxika/Skeptik · GitHub". GitHub.{{cite web}}: CS1 maint: deprecated archival service (link) Wikipedia revision 1206721463, retrieved 2026-11-18
  4. ^ Cotton, Scott. "Two Techniques for Minimizing Resolution Proofs". 13th International Conference on Theory and Applications of Satisfiability Testing, 2010. Wikipedia revision 1206721463, retrieved 2026-11-18
  5. ^ Simone, S.F.; Brutomesso, R.; Sharygina, N. "An Efficient and Flexible Approach to Resolution Proof Reduction". 6th Haifa Verification Conference, 2010. Wikipedia revision 1206721463, retrieved 2026-11-18

Text derived from https://en.wikipedia.org/w/index.php?oldid=1206721463 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001206721463 · captured 2024-02-12 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Proof compression”, snapshot enwiki-001206721463. https://encyclopegia.org/a/proof-compression