Nonuniform reductions and NP-completeness

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

zbMATH Keywords

computational complexityreducibilityNP-completenessnonuniform complexity

Mathematics Subject Classification ID

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