The treewidth of proofs (Q2013559): Difference between revisions

@@ Property / cites work @@
+Space Complexity in Propositional Calculus
@@ Property / cites work: Space Complexity in Propositional Calculus / rank @@
+Normal rank
@@ Property / cites work @@
+A combinatorial characterization of resolution width
+Normal rank
@@ Property / cites work @@
+Partially definable forcing and bounded arithmetic
+Normal rank
@@ Property / cites work @@
+Digraphs
@@ Property / cites work: Digraphs / rank @@
+Normal rank
@@ Property / cites work @@
+Time-space tradeoffs in resolution
@@ Property / cites work: Time-space tradeoffs in resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Size-Space Tradeoffs for Resolution
@@ Property / cites work: Size-Space Tradeoffs for Resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Short proofs are narrow—resolution made simple
@@ Property / cites work: Short proofs are narrow—resolution made simple / rank @@
+Normal rank
@@ Property / cites work @@
+Parity Games and Propositional Proofs
@@ Property / cites work: Parity Games and Propositional Proofs / rank @@
+Normal rank
@@ Property / cites work @@
+A partial k-arboretum of graphs with bounded treewidth
+Normal rank
@@ Property / cites work @@
+Optimality of size-width tradeoffs for resolution
@@ Property / cites work: Optimality of size-width tradeoffs for resolution / rank @@
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+Q5306365
@@ Property / cites work: Q5306365 / rank @@
+Normal rank
@@ Property / cites work @@
+The limits of tractability in resolution-based propositional proof systems
+Normal rank
@@ Property / cites work @@
+Relativization makes contradictions harder for resolution
+Normal rank
@@ Property / cites work @@
+Computer Science Logic
@@ Property / cites work: Computer Science Logic / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of resolution with bounded conjunctions
+Normal rank
@@ Property / cites work @@
+Space bounds for resolution
@@ Property / cites work: Space bounds for resolution / rank @@
+Normal rank
@@ Property / cites work @@
+From Small Space to Small Width in Resolution
@@ Property / cites work: From Small Space to Small Width in Resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Parametrized complexity theory.
@@ Property / cites work: Parametrized complexity theory. / rank @@
+Normal rank
@@ Property / cites work @@
+On Digraph Width Measures in Parameterized Algorithmics
+Normal rank
@@ Property / cites work @@
+The complexity of homomorphism and constraint satisfaction problems seen from the other side
+Normal rank
@@ Property / cites work @@
+Directed tree-width
@@ Property / cites work: Directed tree-width / rank @@
+Normal rank
@@ Property / cites work @@
+The vertex separation number of a graph equals its path-width
+Normal rank
@@ Property / cites work @@
+Searching and pebbling
@@ Property / cites work: Searching and pebbling / rank @@
+Normal rank
@@ Property / cites work @@
+Q4488342
@@ Property / cites work: Q4488342 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds to the size of constant-depth propositional proofs
+Normal rank
@@ Property / cites work @@
+On the weak pigeonhole principle
@@ Property / cites work: On the weak pigeonhole principle / rank @@
+Normal rank
@@ Property / cites work @@
+Combinatorics of first order structures and propositional proof systems
+Normal rank
@@ Property / cites work @@
+Digraph decompositions and monotonicity in digraph searching
+Normal rank
@@ Property / cites work @@
+A new proof of the weak pigeonhole principle
@@ Property / cites work: A new proof of the weak pigeonhole principle / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002818
@@ Property / cites work: Q3002818 / rank @@
+Normal rank
@@ Property / cites work @@
+Infinite Games
@@ Property / cites work: Infinite Games / rank @@
+Normal rank
@@ Property / cites work @@
+Revisiting Space in Proof Complexity: Treewidth and Pathwidth
+Normal rank
@@ Property / cites work @@
+Narrow Proofs May Be Spacious:Separating Space and Width in Resolution
+Normal rank
@@ Property / cites work @@
+Q3689182
@@ Property / cites work: Q3689182 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4737899
@@ Property / cites work: Q4737899 / rank @@
+Normal rank
@@ Property / cites work @@
+Resolution lower bounds for the weak functional pigeonhole principle.
+Normal rank
@@ Property / cites work @@
+Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
+Normal rank
@@ Property / cites work @@
+A New Kind of Tradeoffs in Propositional Proof Complexity
+Normal rank
@@ Property / cites work @@
+A complexity gap for tree resolution
@@ Property / cites work: A complexity gap for tree resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Exponential separation between Res(\(k\)) and Res(\(k+1\)) for \(k \leqslant \varepsilon\log n\)
+Normal rank
@@ Property / cites work @@
+The Complexity of Propositional Proofs
@@ Property / cites work: The Complexity of Propositional Proofs / rank @@
+Normal rank
@@ Property / cites work @@
+A Switching Lemma for Small Restrictions and Lower Bounds for <i>k</i>-DNF Resolution
+Normal rank
@@ Property / cites work @@
+Short resolution proofs for a sequence of tricky formulas
+Normal rank