Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-113 | 19th August 2013 22:36

Revisiting Space in Proof Complexity: Treewidth and Pathwidth

RSS-Feed




TR13-113
Authors: Moritz Müller, Stefan Szeider
Publication: 24th August 2013 18:35
Downloads: 3068
Keywords: 


Abstract:

So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. The ordered pathwidth of a proof is shown to be roughly the same as its formula space. Length-space lower bounds for R(k)-refutations are generalized to arbitrary infinity axioms and strengthened in that the space measure is relaxed to ordered treewidth.



ISSN 1433-8092 | Imprint