Nonuniform reductions and NP-completeness (Q2158296): Difference between revisions

@@ Property / DOI @@
-.1007/s00224-022-10083-y
@@ Property / DOI: 10.1007/s00224-022-10083-y / rank @@
-Normal rank
@@ Property / MaRDI profile type @@
+Publication
@@ Property / MaRDI profile type: Publication / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s00224-022-10083-y
+Normal rank
@@ Property / OpenAlex ID @@
+W2783885456
@@ Property / OpenAlex ID: W2783885456 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4474202
@@ Property / cites work: Q4474202 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Complexity
@@ Property / cites work: The Complexity of Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Power from Random Strings
@@ Property / cites work: Power from Random Strings / rank @@
+Normal rank
@@ Property / cites work @@
+Q4348122
@@ Property / cites work: Q4348122 / rank @@
+Normal rank
@@ Property / cites work @@
+Resource bounded randomness and weakly complete problems
+Normal rank
@@ Property / cites work @@
+\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
+Normal rank
@@ Property / cites work @@
+Q4321931
@@ Property / cites work: Q4321931 / rank @@
+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 @@
+Hard sets are hard to find
@@ Property / cites work: Hard sets are hard to find / rank @@
+Normal rank
@@ Property / cites work @@
+Identifying an honest EXP NP oracle among many
@@ Property / cites work: Identifying an honest EXP NP oracle among many / rank @@
+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 @@
+Hardness hypotheses, derandomization, and circuit complexity
+Normal rank
@@ Property / cites work @@
+Autoreducibility of NP-complete sets under strong hypotheses
+Normal rank
@@ Property / cites work @@
+Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
+Normal rank
@@ Property / cites work @@
+Circuit minimization problem
@@ Property / cites work: Circuit minimization problem / rank @@
+Normal rank
@@ Property / cites work @@
+Turing machines that take advice
@@ Property / cites work: Turing machines that take advice / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+Almost everywhere high nonuniform complexity
@@ Property / cites work: Almost everywhere high nonuniform complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Q4359463
@@ Property / cites work: Q4359463 / rank @@
+Normal rank
@@ Property / cites work @@
+Cook versus Karp-Levin: Separating completeness notions if NP is not small
+Normal rank
@@ Property / cites work @@
+Q4298260
@@ Property / cites work: Q4298260 / rank @@
+Normal rank
@@ Property / cites work @@
+Bi-immunity separates strong NP-completeness notions
+Normal rank
@@ Property / cites work @@
+NP is as easy as detecting unique solutions
@@ Property / cites work: NP is as easy as detecting unique solutions / rank @@
+Normal rank
@@ Property / DOI @@
+.1007/S00224-022-10083-Y
@@ Property / DOI: 10.1007/S00224-022-10083-Y / rank @@
+Normal rank