Nonuniform reductions and NP-completeness
From MaRDI portal
Publication:2158296
DOI10.1007/S00224-022-10083-YOpenAlexW2783885456MaRDI QIDQ2158296FDOQ2158296
Hadi Shafei, John M. Hitchcock
Publication date: 26 July 2022
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-022-10083-y
Recommendations
- Nonuniform reductions and NP-completeness
- Nondiamond theorems for polynomial time reducibility
- Decompositions of nondeterministic reductions
- scientific article; zbMATH DE number 3960995
- scientific article; zbMATH DE number 915981
- Autoreducibility of NP-complete sets
- scientific article; zbMATH DE number 3963808
- Reductions, completeness and the hardness of approximability
- scientific article; zbMATH DE number 3889514
- Complexity of nonuniform computations for certain discrete problems
Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Computability and recursion theory (03Dxx)
Cites Work
- Title not available (Why is that?)
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Title not available (Why is that?)
- Almost everywhere high nonuniform complexity
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- NP is as easy as detecting unique solutions
- Title not available (Why is that?)
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Resource bounded randomness and weakly complete problems
- Bi-immunity separates strong NP-completeness notions
- Title not available (Why is that?)
- Turing machines that take advice
- Circuit minimization problem
- Title not available (Why is that?)
- Power from Random Strings
- Non-uniform reductions
- Comparing reductions to NP-complete sets
- Hardness hypotheses, derandomization, and circuit complexity
- Hard sets are hard to find
- Autoreducibility of NP-complete sets under strong hypotheses
- The Complexity of Complexity
- Identifying an honest EXP NP oracle among many
Cited In (10)
- On Unapproximable Versions of $NP$-Complete Problems
- The Shrinking Property for NP and coNP
- Non-uniform reductions
- Title not available (Why is that?)
- The shrinking property for NP and coNP
- Reducing the number of solutions of NP functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- UG-hardness to NP-hardness by losing half
- Reductions between disjoint NP-pairs
This page was built for publication: Nonuniform reductions and NP-completeness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2158296)
