Paper Info
Title
Resolution Proofs, Exponential Bounds, and Kolmogorov Complexity
Abstract
We prove an exponential lower bound for the length of any resolution proof for the same set of clauses as the one used by Urquhart [13]. Our contribution is a significant simplification in the proof and strengthening of the bound, as compared to [13]. We use on the one hand a simplification similar to the one suggested by Beame and Pitassi in [1] for the case of the pidgeon hole clauses. Additionally, we base our construction on a simpler version of expander graphs than the ones used in [13]. These expander graphs are located in the core of the construction. We show the existence of our expanders by a Kolmogorov complexity argument which has not been used before in this context and might be of independent interest since the applicability of this method is quite general.
Year
DOI
Venue
1997
10.1007/BFb0029954
MFCS
Keywords
Field
DocType
kolmogorov complexity,exponential bounds,resolution proofs,lower bound,expander graph
Graph theory,Discrete mathematics,Combinatorics,Expander graph,Kolmogorov complexity,Upper and lower bounds,Conjunctive normal form,Mathematical proof,Kolmogorov structure function,Chain rule for Kolmogorov complexity,Mathematics
Conference
ISBN
Citations 
PageRank 
3-540-63437-1
3
0.54
References 
Authors
10
1
Name
Order
Citations
PageRank
Uwe Schöning1998105.69