loading...
The Complexity of Treelike Systems over λ-Local Formulae
Amherst, Massachusetts June 21-June 24
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2004.131379819th Annual IEEE Conference on Comput ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Nicola Galesi, Universitat Politécnica de Catalunya
Neil Thapen, University of Toronto
We describ e a system LK(c[\lambda]) for refuting CNF formulae, as a restriction of the sequent calculus in which every formula in a sequent is defined over at most \lambda variables. This further generalizes the system Res(k), a generalization of Resolution to k-DNF introduced in [9]. We adapt the Pudlák-Impagliazzo game ([11]) to prove lower bounds for treelike LK(c[\lambda]). We show that dynamic satisfiability, which was introduced in [6] to study resolution space complexity, is a sufficient "but not necessary" condition to obtain exponential lower bounds.
Citation:
Nicola Galesi, Neil Thapen, "The Complexity of Treelike Systems over λ-Local Formulae," ccc, pp.68-74, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.