Minimum propositional proof length is NP-hard to linearly approximate (Q2732273): Difference between revisions

@@ Property / author @@
+Samuel R. Buss
@@ Property / author: Samuel R. Buss / rank @@
+Normal rank
@@ 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.2307/2694916
@@ Property / full work available at URL: https://doi.org/10.2307/2694916 / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2006906201
@@ Property / OpenAlex ID: W2006906201 / rank @@
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating minimization problems
+Normal rank
@@ Property / cites work @@
+Q3002852
@@ Property / cites work: Q3002852 / rank @@
+Normal rank
@@ Property / cites work @@
+The hardness of approximate optima in lattices, codes, and systems of linear equations
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+Some remarks on lengths of propositional proofs
@@ Property / cites work: Some remarks on lengths of propositional proofs / rank @@
+Normal rank