The treewidth of proofs
From MaRDI portal
Publication:2013559
DOI10.1016/j.ic.2017.05.005zbMath1423.03244OpenAlexW2694154901WikidataQ114667612 ScholiaQ114667612MaRDI QIDQ2013559
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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Relativization makes contradictions harder for resolution
- The limits of tractability in resolution-based propositional proof systems
- Digraph decompositions and monotonicity in digraph searching
- Combinatorics of first order structures and propositional proof systems
- Exponential separation between Res(\(k\)) and Res(\(k+1\)) for \(k \leqslant \varepsilon\log n\)
- The vertex separation number of a graph equals its path-width
- A partial k-arboretum of graphs with bounded treewidth
- Resolution lower bounds for the weak functional pigeonhole principle.
- Optimality of size-width tradeoffs for resolution
- A complexity gap for tree resolution
- Searching and pebbling
- Directed tree-width
- Space bounds for resolution
- On the complexity of resolution with bounded conjunctions
- Short resolution proofs for a sequence of tricky formulas
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Partially definable forcing and bounded arithmetic
- A combinatorial characterization of resolution width
- Parametrized complexity theory.
- On the weak pigeonhole principle
- Revisiting Space in Proof Complexity: Treewidth and Pathwidth
- Space Complexity in Propositional Calculus
- A New Kind of Tradeoffs in Propositional Proof Complexity
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Size-Space Tradeoffs for Resolution
- On Digraph Width Measures in Parameterized Algorithmics
- The relative efficiency of propositional proof systems
- Lower bounds to the size of constant-depth propositional proofs
- Short proofs are narrow—resolution made simple
- Infinite Games
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- Parity Games and Propositional Proofs
- Narrow Proofs May Be Spacious:Separating Space and Width in Resolution
- From Small Space to Small Width in Resolution
- Computer Science Logic
- Time-space tradeoffs in resolution
- The Complexity of Propositional Proofs
- Digraphs
- A new proof of the weak pigeonhole principle
This page was built for publication: The treewidth of proofs
