Nonuniform reductions and NP-completeness
From MaRDI portal
Publication:2158296
DOI10.1007/s00224-022-10083-yOpenAlexW2783885456MaRDI QIDQ2158296
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
Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Computability and recursion theory (03Dxx)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- Turing machines that take advice
- Comparing reductions to NP-complete sets
- Hardness hypotheses, derandomization, and circuit complexity
- NP is as easy as detecting unique solutions
- Almost everywhere high nonuniform complexity
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Resource bounded randomness and weakly complete problems
- Autoreducibility of NP-complete sets under strong hypotheses
- Bi-immunity separates strong NP-completeness notions
- Non-uniform reductions
- Hard sets are hard to find
- The Complexity of Complexity
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Circuit minimization problem
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Identifying an honest EXP NP oracle among many
- Power from Random Strings
This page was built for publication: Nonuniform reductions and NP-completeness
