Characterizing Tseitin-formulas with short regular resolution refutations (Q2118291): Difference between revisions

@@ Property / cites work @@
+Q3002781
@@ Property / cites work: Q3002781 / rank @@
+Normal rank
@@ Property / cites work @@
+Satisfiability, branch-width and Tseitin tautologies
+Normal rank
@@ Property / cites work @@
+Clique is hard on average for regular resolution
@@ Property / cites work: Clique is hard on average for regular resolution / 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 @@
+Strong ETH holds for regular resolution
@@ Property / cites work: Strong ETH holds for regular resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Hard examples for the bounded depth Frege proof system
+Normal rank
@@ Property / cites work @@
+Safe separators for treewidth
@@ Property / cites work: Safe separators for treewidth / rank @@
+Normal rank
@@ Property / cites work @@
+Decomposable negation normal form
@@ Property / cites work: Decomposable negation normal form / rank @@
+Normal rank
@@ Property / cites work @@
+Q4411139
@@ Property / cites work: Q4411139 / rank @@
+Normal rank
@@ Property / cites work @@
+A machine program for theorem-proving
@@ Property / cites work: A machine program for theorem-proving / rank @@
+Normal rank
@@ Property / cites work @@
+A Computing Procedure for Quantification Theory
@@ Property / cites work: A Computing Procedure for Quantification Theory / rank @@
+Normal rank
@@ Property / cites work @@
+Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
+Normal rank
@@ Property / cites work @@
+Cops-robber games and the resolution of Tseitin formulas
+Normal rank
@@ Property / cites work @@
+Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs.
+Normal rank
@@ Property / cites work @@
+Regular Resolution Versus Unrestricted Resolution
@@ Property / cites work: Regular Resolution Versus Unrestricted Resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Parameters Tied to Treewidth
@@ Property / cites work: Parameters Tied to Treewidth / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP
+Normal rank
@@ Property / cites work @@
+Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
+Normal rank
@@ Property / cites work @@
+Search Problems in the Decision Tree Model
@@ Property / cites work: Search Problems in the Decision Tree Model / rank @@
+Normal rank
@@ Property / cites work @@
+On the read-once property of branching programs and CNFs of bounded treewidth
+Normal rank
@@ Property / cites work @@
+Q5593816
@@ Property / cites work: Q5593816 / rank @@
+Normal rank
@@ Property / cites work @@
+Hard examples for resolution
@@ Property / cites work: Hard examples for resolution / rank @@
+Normal rank
@@ Property / cites work @@
+A Near-Optimal Separation of Regular and General Resolution
+Normal rank
@@ Property / cites work @@
+Simplified and improved separations between regular and general resolution by lifting
+Normal rank