Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-044 | 12th May 2003 00:00

A Combinatorial Characterization of Treelike Resolution Space

RSS-Feed




TR03-044
Authors: Juan Luis Esteban, Jacobo Toran
Publication: 6th June 2003 19:43
Downloads: 4039
Keywords: 


Abstract:

We show that the Player-Adversary game from a paper
by Pudlak and Impagliazzo played over
CNF propositional formulas gives
an exact characterization of the space needed
in treelike resolution refutations. This
characterization is purely combinatorial
and independent of the notion of resolution.
We use this characterization to give for the first time
a separation between the space needed in tree-like and
general resolution.



ISSN 1433-8092 | Imprint