Nonuniform reductions and NP-completeness

DOI10.1007/S00224-022-10083-YMaRDI QIDQ2158296zbMATH OpenOpenAlexFDO

Authors John M. Hitchcock, Hadi Shafei

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 complexitynonuniform complexityNP-completenessreducibility

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Computability and recursion theory (03Dxx)

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

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 719756 (Why is no real title available?)
• scientific article; zbMATH DE number 1048036 (Why is no real title available?)
• scientific article; zbMATH DE number 1072536 (Why is no real title available?)
• scientific article; zbMATH DE number 2081089 (Why is no real title available?)
• Almost everywhere high nonuniform complexity
• Autoreducibility of NP-complete sets under strong hypotheses
• Bi-immunity separates strong NP-completeness notions
• Circuit minimization problem
• Comparing reductions to NP-complete sets
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Hard sets are hard to find
• Hardness hypotheses, derandomization, and circuit complexity
• Identifying an honest \(\mathrm{EXP}^{\mathrm{NP}}\) oracle among many
• NP is as easy as detecting unique solutions
• Non-uniform reductions
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Power from Random Strings
• Resource bounded randomness and weakly complete problems
• The Complexity of Complexity
• Turing machines that take advice
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs

Cited in

(10)

• The shrinking property for NP and coNP
• Non-uniform reductions
• The Shrinking Property for NP and coNP
• Reducing the number of solutions of NP functions
• scientific article; zbMATH DE number 3963808 (Why is no real title available?)
• UG-hardness to NP-hardness by losing half
• scientific article; zbMATH DE number 3960995 (Why is no real title available?)
• On Unapproximable Versions of $NP$-Complete Problems
• Reductions between disjoint NP-pairs
• scientific article; zbMATH DE number 4126690 (Why is no real title available?)

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)