Collapsing and separating completeness notions under average-case and worst-case hypotheses (Q693053): Difference between revisions

@@ Property / OpenAlex ID @@
+W1568724636
@@ Property / OpenAlex ID: W1568724636 / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Some connections between bounded query classes and non-uniform complexity.
+Normal rank
@@ Property / cites work @@
+Separating NP-completeness notions under strong hypotheses
+Normal rank
@@ Property / cites work @@
+Q4131649
@@ Property / cites work: Q4131649 / rank @@
+Normal rank
@@ Property / cites work @@
+On being incoherent without being very hard
@@ Property / cites work: On being incoherent without being very hard / rank @@
+Normal rank
@@ Property / cites work @@
+\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+Non-uniform reductions
@@ Property / cites work: Non-uniform reductions / rank @@
+Normal rank
@@ Property / cites work @@
+Completeness for nondeterministic complexity classes
+Normal rank
@@ Property / cites work @@
+The complexity of theorem-proving procedures
@@ Property / cites work: The complexity of theorem-proving procedures / rank @@
+Normal rank
@@ Property / cites work @@
+On coherence, random-self-reducibility, and self-correction
+Normal rank
@@ Property / cites work @@
+The power of adaptiveness and additional queries in random-self- reductions
+Normal rank
@@ Property / cites work @@
+Q3549693
@@ Property / cites work: Q3549693 / rank @@
+Normal rank
@@ Property / cites work @@
+Complete Problems and Strong Polynomial Reducibilities
+Normal rank
@@ Property / cites work @@
+On Constructing 1-1 One-Way Functions
@@ Property / cites work: On Constructing 1-1 One-Way Functions / rank @@
+Normal rank
@@ Property / cites work @@
+\(p\)-Selective sets and reducing search to decision vs. self-reducibility
+Normal rank
@@ Property / cites work @@
+Comparing reductions to NP-complete sets
@@ Property / cites work: Comparing reductions to NP-complete sets / rank @@
+Normal rank
@@ Property / cites work @@
+Partial bi-immunity, scaled dimension, and NP-completeness
+Normal rank
@@ Property / cites work @@
+Q4252738
@@ Property / cites work: Q4252738 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4526985
@@ Property / cites work: Q4526985 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3285920
@@ Property / cites work: Q3285920 / rank @@
+Normal rank
@@ Property / cites work @@
+A comparison of polynomial time reducibilities
@@ Property / cites work: A comparison of polynomial time reducibilities / rank @@
+Normal rank
@@ Property / cites work @@
+Measure, Stochasticity, and the Density of Hard Languages
+Normal rank
@@ Property / cites work @@
+Cook versus Karp-Levin: Separating completeness notions if NP is not small
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+Separation of NP-Completeness Notions
@@ Property / cites work: Separation of NP-Completeness Notions / rank @@
+Normal rank
@@ Property / cites work @@
+Bi-immunity separates strong NP-completeness notions
+Normal rank
@@ Property / cites work @@
+Pseudorandom generators without the XOR lemma
@@ Property / cites work: Pseudorandom generators without the XOR lemma / rank @@
+Normal rank
@@ Property / cites work @@
+A comparison of polynomial time completeness notions
+Normal rank