Short proofs are narrow—resolution made simple
Authors:
- Eli Ben-SassonEBEli Ben-Sasson
Top Cited Papers
Open Access
- 1 March 2001
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 48 (2) , 149-169
Abstract
The width of a Resolution proof is defined to be the maximal number of literals in any clause of the proof. In this paper, we relate proof width to proof length (=size), in both general Resolution, and its tree-like variant. The following consequences of these relations reveal width as a crucial “resource” of Resolution proofs. In one direction, the relations allow us to give simple, unified proofs for almost all known exponential lower bounds on size of resolution proofs, as well as several interesting new ones. They all follow from width lower bounds, and we show how these follow from natural expansion property of clauses of the input tautology. In the other direction, the width-size relations naturally suggest a simple dynamic programming procedure for automated theorem proving—one which simply searches for small width proofs. This relation guarantees that the runnuing time (and thus the size of the produced proof) is at most quasi-polynomial in the smallest tree-like proof. This algorithm is never much worse than any of the recursive automated provers (such as DLL) used in practice. In contrast, we present a family of tautologies on which it is exponentially faster.Keywords
This publication has 10 references indexed in Scilit:
- Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus1997
- Using the Groebner basis algorithm to find proofs of unsatisfiability1996
- Natural proofs1994
- Resolution proofs of generalized pigeonhole principlesTheoretical Computer Science, 1988
- Many hard examples for resolutionJournal of the ACM, 1988
- Hard examples for resolutionJournal of the ACM, 1987
- The intractability of resolutionTheoretical Computer Science, 1985
- The relative efficiency of propositional proof systemsThe Journal of Symbolic Logic, 1979
- On Resolution with Clauses of Bounded SizeSIAM Journal on Computing, 1977
- A machine program for theorem-provingCommunications of the ACM, 1962