Autoreducibility of NP-complete sets

DOI10.4230/LIPICS.STACS.2016.42zbMATH Open1388.68087arXiv1601.05494MaRDI QIDQ4601894FDOQ4601894

Authors: John M. Hitchcock, Hadi Shafei 

Publication date: 24 January 2018

Full work available at URL: https://arxiv.org/abs/1601.05494

Recommendations

• Autoreducibility of NP-complete sets under strong hypotheses
• Probabilistic autoreductions
• Autoreducibility, mitoticity, and immunity
• Separating Complexity Classes Using Autoreducibility
• Mathematical Foundations of Computer Science 2005

zbMATH Keywords

computational complexityNP-completenessgenericityautoreducibility

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)

Cited In (11)

• On the reducibility of sets inside NP to sets with low information content
• Autoreducibility of NP-complete sets under strong hypotheses
• Structural properties of nonautoreducible sets
• Mathematical Foundations of Computer Science 2005
• Probabilistic autoreductions
• On the autoreducibility of functions
• Automatic Evaluation of Reductions between NP-Complete Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nonuniform reductions and NP-completeness
• Nonuniform reductions and NP-completeness

This page was built for publication: Autoreducibility of NP-complete sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601894)