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.