Lecture Notes in Computer Science, 2002, Volume 2380/2002, 779, DOI: 10.1007/3-540-45465-9_20

On the Complexity of Resolution with Bounded Conjunctions
Extended Abstract

Juan Luis Esteban, Nicola Galesi and Jochen Messner

View Related Documents

Abstract

We analyze size and space complexity of Res(k), a family of proof systems introduced by Krajíček in [16] which extend Resolution by allowing disjunctions of conjunctions of up to k ≥ 1 literals. We prove the following results: (1) The treelike Res(k) proof systems form a strict hierarchy with respect to proof size and also with respect to space. (2) Resolution polynomially simulates treelike Res(k), and is almost exponentially separated from treelike Res(k). (3) The space lower bounds known for Resolution also carry over to Res(k). We obtain almost optimal space lower bounds for PHPn, GTn, Random Formulas, CTn, and Tseitin Tautologies.
The authors were partly supported by the DAAD project Acciones integradas Hispano-Alemanas no. 70116. J.L. Esteban was also partly supported by MEC through grant PB 98-0937-C04 (FRESCO Project). N. Galesi was also partly supported by Spanish grant TIC2001-1577-C03-02 and by CSERC Canadian funds.

Fulltext Preview

Image of the first page of the fulltext document