We describe a system for refuting CNF formulas as a restriction fo the sequent calculus where every formula is defined over at most lambda variables. This further generalizes the Res8k) systems. We adapt the pudalk-Impagliiazzo game to prove lower bounds for the treelike version of this system and we obtain exponential lower bounds
The Complexity of Treelike Systems over lamdda-Local Formulae / Galesi, Nicola; Thapen, N.. - STAMPA. - 19:(2004), pp. 68-74. (Intervento presentato al convegno IEEE Conference on Computational Complexity. tenutosi a Amherst, Massachusetts, USA) [10.1109/CCC.2004.1313798].
The Complexity of Treelike Systems over lamdda-Local Formulae
GALESI, NICOLA
Primo
;
2004
Abstract
We describe a system for refuting CNF formulas as a restriction fo the sequent calculus where every formula is defined over at most lambda variables. This further generalizes the Res8k) systems. We adapt the pudalk-Impagliiazzo game to prove lower bounds for the treelike version of this system and we obtain exponential lower boundsFile allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
