Document Open Access Logo

Autoreducibility of NP-Complete Sets

Authors John M. Hitchcock, Hadi Shafei

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2016.42.pdf
  • Filesize: 0.55 MB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • computational complexity
  • NP-completeness
  • autoreducibility
  • genericity

Metrics

Abstract

We study the polynomial-time autoreducibility of NP-complete sets and obtain separations under strong hypotheses for NP. Assuming there is a p-generic set in NP, we show the following:

- For every k >= 2, there is a k-T-complete set for NP that is k-T autoreducible, but is not k-tt autoreducible or (k-1)-T autoreducible.

- For every k >= 3, there is a k-tt-complete set for NP that is k-tt autoreducible, but is not (k-1)-tt autoreducible or (k-2)-T autoreducible.

- There is a tt-complete set for NP that is tt-autoreducible, but is not btt-autoreducible.
  
Under the stronger assumption that there is a p-generic set in NP cap coNP, we show:

- For every k >= 2, there is a k-tt-complete set for NP that is k-tt autoreducible, but is not (k-1)-T autoreducible.
  
Our proofs are based on constructions from separating NP-completeness notions. For example, the construction of a 2-T-complete set for NP that is not 2-tt-complete also separates 2-T-autoreducibility from 2-tt-autoreducibility.

Cite As Get BibTex

John M. Hitchcock and Hadi Shafei. Autoreducibility of NP-Complete Sets. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 42:1-42:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.STACS.2016.42

Author Details

John M. Hitchcock
Hadi Shafei

References

  1. K. Ambos-Spies. P-mitotic sets. In Logic and Machines: Decision Problems and Complexity, Proceedings of the Symposium "Rekursive Kombinatorik" held from May 23-28, 1983 at the Institut für Mathematische Logik und Grundlagenforschung der Universität Münster/Westfalen, pages 1-23, 1983. URL: http://dx.doi.org/10.1007/3-540-13331-3_30.
  2. K. Ambos-Spies and L. Bentzien. Separating NP-completeness notions under strong hypotheses. Journal of Computer and System Sciences, 61(3):335-361, 2000. Google Scholar
  3. K. Ambos-Spies, H. Fleischhack, and H. Huwig. Diagonalizations over polynomial time computable sets. Theoretical Computer Science, 51:177-204, 1987. Google Scholar
  4. R. Beigel and J. Feigenbaum. On being incoherent without being very hard. Computational Complexity, 2:1-17, 1992. Google Scholar
  5. H. Buhrman, L. Fortnow, D. van Melkebeek, and L. Torenvliet. Separating complexity classes using autoreducibility. SIAM Journal on Computing, 29(5):1497-1520, 2000. Google Scholar
  6. H. Buhrman, B. Hescott, S. Homer, and L. Torenvliet. Non-uniform reductions. Theory of Computing Systems, 47(2):317-341, 2010. URL: http://dx.doi.org/10.1007/s00224-008-9163-5.
  7. H. Buhrman and L. Torenvliet. A Post’s program for complexity theory. Bulletin of the EATCS, 85:41-51, 2005. Google Scholar
  8. C. Glaßer, M. Ogihara, A. Pavan, A. L. Selman, and L. Zhang. Autoreducibility, mitoticity, and immunity. J. Comput. Syst. Sci., 73(5):735-754, 2007. URL: http://dx.doi.org/10.1016/j.jcss.2006.10.020.
  9. J. M. Hitchcock and A. Pavan. Comparing reductions to NP-complete sets. Information and Computation, 205(5):694-706, 2007. URL: http://dx.doi.org/10.1016/j.ic.2006.10.005.
  10. J. M. Hitchcock and A. Pavan. Hardness hypotheses, derandomization, and circuit complexity. Computational Complexity, 17(1):119-146, 2008. URL: http://dx.doi.org/10.1007/s00037-008-0241-5.
  11. R. E. Ladner, N. A. Lynch, and A. L. Selman. A comparison of polynomial-time reducibilities. Theoretical Computer Science, 1(2):103-123, 1975. Google Scholar
  12. J. H. Lutz and E. Mayordomo. Cook versus Karp-Levin: Separating completeness notions if NP is not small. Theoretical Computer Science, 164(1-2):141-163, 1996. Google Scholar
  13. D. T. Nguyen and A. L. Selman. Non-autoreducible sets for NEXP. In 31st International Symposium on Theoretical Aspects of Computer Science, pages 590-601, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2014.590.
  14. A. Pavan and A. L. Selman. Bi-immunity separates strong NP-completeness notions. Information and Computation, 188(1):116-126, 2004. Google Scholar
  15. B. Trakhtenbrot. On autoreducibility. Dokl. Akad. Nauk SSSR, 192(6):1224-–1227, 1970. Translation in Soviet Math. Dokl. 11(3): 814–817, 1970. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact