Hard Instances of Algorithms and Proof Systems (Q5892128): Difference between revisions

@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+Do there exist complete sets for promise classes?
@@ Property / cites work: Do there exist complete sets for promise classes? / rank @@
+Normal rank
@@ Property / cites work @@
+Results on resource-bounded measure
@@ Property / cites work: Results on resource-bounded measure / rank @@
+Normal rank
@@ Property / cites work @@
+On p-Optimal Proof Systems and Logics for PTIME
@@ Property / cites work: On p-Optimal Proof Systems and Logics for PTIME / rank @@
+Normal rank
@@ Property / cites work @@
+ON OPTIMAL INVERTERS
@@ Property / cites work: ON OPTIMAL INVERTERS / rank @@
+Normal rank
@@ Property / cites work @@
+If NP languages are hard on the worst-case, then it is easy to find their hard instances
+Normal rank
@@ Property / cites work @@
+Completeness, Approximation and Density
@@ Property / cites work: Completeness, Approximation and Density / rank @@
+Normal rank
@@ Property / cites work @@
+Q4258579
@@ Property / cites work: Q4258579 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal proof systems imply complete sets for promise classes
+Normal rank
@@ Property / cites work @@
+Observations on measure and lowness for \(\Delta_ 2^ p\)
+Normal rank
@@ Property / cites work @@
+Q4359463
@@ Property / cites work: Q4359463 / rank @@
+Normal rank
@@ Property / cites work @@
+Almost every set in exponential time is P-bi-immune
+Normal rank
@@ Property / cites work @@
+Q4251070
@@ Property / cites work: Q4251070 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4708605
@@ Property / cites work: Q4708605 / rank @@
+Normal rank
@@ Property / cites work @@
+Speedup for natural problems and noncomputability
@@ Property / cites work: Speedup for natural problems and noncomputability / rank @@
+Normal rank
@@ Property / cites work @@
+On an optimal propositional proof system and the structure of easy subsets of TAUT.
+Normal rank
@@ Property / cites work @@
+Q5422270
@@ Property / cites work: Q5422270 / rank @@
+Normal rank