The treewidth of proofs

DOI10.1016/J.IC.2017.05.005MaRDI QIDQ2013559zbMATH OpenOpenAlexWikidataFDO

Authors Moritz Müller, Stefan Szeider

Publication date 8 August 2017

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2017.05.005

zbMATH Keywords

treewidthpathwidthresolutionproof complexityinfinity axiomsproof space

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Recommendations

• Revisiting space in proof complexity: treewidth and pathwidth
• scientific article; zbMATH DE number 7561762
• Tree-width in algebraic complexity
• Quantified propositional logic and the number of lines of tree-like proofs
• The Complexity of Propositional Proofs
• The Complexity of Propositional Proofs
• scientific article; zbMATH DE number 1860672
• scientific article; zbMATH DE number 1156870
• Lifting lower bounds for tree-like proofs
• scientific article; zbMATH DE number 785053

Cites work

• scientific article; zbMATH DE number 3912375 (Why is no real title available?)
• scientific article; zbMATH DE number 1470716 (Why is no real title available?)
• scientific article; zbMATH DE number 2087215 (Why is no real title available?)
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• A combinatorial characterization of resolution width
• A complexity gap for tree resolution
• A new kind of tradeoffs in propositional proof complexity
• A new proof of the weak pigeonhole principle
• A partial k-arboretum of graphs with bounded treewidth
• Can you beat treewidth?
• Combinatorics of first order structures and propositional proof systems
• Computer Science Logic
• Digraph decompositions and monotonicity in digraph searching
• Digraphs
• Directed tree-width
• Exponential separation between Res(k) and Res(k+1) for k n
• From small space to small width in resolution
• Infinite Games
• Logical foundations of proof complexity
• Lower bounds to the size of constant-depth propositional proofs
• Narrow proofs may be spacious: separating space and width in resolution
• On digraph width measures in parameterized algorithmics
• On the complexity of resolution with bounded conjunctions
• On the weak pigeonhole principle
• Optimality of size-width tradeoffs for resolution
• Parametrized complexity theory.
• Parity Games and Propositional Proofs
• Partially definable forcing and bounded arithmetic
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Relativization makes contradictions harder for resolution
• Resolution lower bounds for the weak functional pigeonhole principle.
• Revisiting space in proof complexity: treewidth and pathwidth
• Searching and pebbling
• Short proofs are narrow—resolution made simple
• Short resolution proofs for a sequence of tricky formulas
• Size-space tradeoffs for resolution
• Space Complexity in Propositional Calculus
• Space bounds for resolution
• The Complexity of Propositional Proofs
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The limits of tractability in resolution-based propositional proof systems
• The relative efficiency of propositional proof systems
• The vertex separation number of a graph equals its path-width
• Time-space tradeoffs in resolution, superpolynomial lower bounds for superlinear space

Cited in

(4)

• An algorithmic metatheorem for directed treewidth
• Revisiting space in proof complexity: treewidth and pathwidth
• Lifting lower bounds for tree-like proofs
• scientific article; zbMATH DE number 7650825 (Why is no real title available?)

This page was built for publication: The treewidth of proofs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2013559)