An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances (Q2980924): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/978-3-319-53925-6_28
+Normal rank
@@ Property / OpenAlex ID @@
+W2588004537
@@ Property / OpenAlex ID: W2588004537 / rank @@
+Normal rank
@@ Property / cites work @@
+Minimum propositional proof length is NP-hard to linearly approximate
+Normal rank
@@ Property / cites work @@
+Resolution Is Not Automatizable Unless W[P] Is Tractable
+Normal rank
@@ Property / cites work @@
+Satisfiability, branch-width and Tseitin tautologies
+Normal rank
@@ Property / cites work @@
+Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
+Normal rank
@@ Property / cites work @@
+Narrow Proofs May Be Maximally Long
@@ Property / cites work: Narrow Proofs May Be Maximally Long / 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 @@
+A linear time algorithm for finding tree-decompositions of small treewidth
+Normal rank
@@ Property / cites work @@
+Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
+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 @@
+The intractability of resolution
@@ Property / cites work: The intractability of resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Conjunctive-query containment and constraint satisfaction
+Normal rank
@@ Property / cites work @@
+Tree-width, path-width, and cutwidth
@@ Property / cites work: Tree-width, path-width, and cutwidth / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithms for propositional model counting
@@ Property / cites work: Algorithms for propositional model counting / rank @@
+Normal rank
@@ Property / cites work @@
+Constructive linear time algorithms for branchwidth
+Normal rank