The NP-hardness of finding a directed acyclic graph for regular resolution (Q924157): 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.1016/j.tcs.2008.01.039
+Normal rank
@@ Property / OpenAlex ID @@
+W2084517146
@@ Property / OpenAlex ID: W2084517146 / rank @@
+Normal rank
@@ Property / cites work @@
+Minimum propositional proof length is NP-hard to linearly approximate
+Normal rank
@@ Property / cites work @@
+An exponential separation between regular and general resolution
+Normal rank
@@ Property / cites work @@
+Resolution Is Not Automatizable Unless W[P] Is Tractable
+Normal rank
@@ Property / cites work @@
+On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+On the complexity of regular resolution and the Davis-Putnam procedure
+Normal rank
@@ Property / cites work @@
+Regular Resolution Versus Unrestricted Resolution
@@ Property / cites work: Regular Resolution Versus Unrestricted Resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Q4699307
@@ Property / cites work: Q4699307 / rank @@
+Normal rank
@@ Property / cites work @@
+Regular resolution lower bounds for the weak pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Q3682461
@@ Property / cites work: Q3682461 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4539605
@@ Property / cites work: Q4539605 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5604434
@@ Property / cites work: Q5604434 / rank @@
+Normal rank