loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th Annual IEEE Conference on Computational Complexity (CCC'04)
The Complexity of Treelike Systems over λ-Local Formulae
Amherst, Massachusetts
June 21-June 24
ISBN: 0-7695-2120-7
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.