We analyze size and space complexity of Res(k), a family of propositional proof systems introduced by Krajíček in (Fund. Math. 170 (1-3) (2001) 123) which extend Resolution by allowing disjunctions of conjunctions of up to k≥1 literals. We show that the treelike Res(k) proof systems form a strict hierarchy with respect to proof size and also with respect to space. Moreover Resolution, while simulating treelike Res(k), is almost exponentially separated from treelike Res(k). To study space complexity for general Res(k) we introduce the concept of dynamical satisfiability which allows us to prove in a unified way all known space lower bounds for Resolution and to extend them to Res(k). © 2004 Elsevier B.V. All rights reserved.
On the complexity of resolution with bounded conjunctions / Juan Luis, Esteban; Galesi, Nicola; Jochen, Messner. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 321:2-3(2004), pp. 347-370. [10.1016/j.tcs.2004.04.004]
On the complexity of resolution with bounded conjunctions
GALESI, NICOLA;
2004
Abstract
We analyze size and space complexity of Res(k), a family of propositional proof systems introduced by Krajíček in (Fund. Math. 170 (1-3) (2001) 123) which extend Resolution by allowing disjunctions of conjunctions of up to k≥1 literals. We show that the treelike Res(k) proof systems form a strict hierarchy with respect to proof size and also with respect to space. Moreover Resolution, while simulating treelike Res(k), is almost exponentially separated from treelike Res(k). To study space complexity for general Res(k) we introduce the concept of dynamical satisfiability which allows us to prove in a unified way all known space lower bounds for Resolution and to extend them to Res(k). © 2004 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
