A combinatorial characterization of treelike resolution space
We show that the Player-Adversary game of Pudlak and Impagliazzo [A lower bound for DLL algorithms for k-SAT, in: Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms, 2000, pp. 128-136] 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 treelike and general resolution. (C) 2003 Elsevier B.V. All rights reserved.
treelike resolution complexity measures for resolution theory of computation