Document Open Access Logo

Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis

Authors Debasis Mandal, A. Pavan, Rajeswari Venugopalan

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2014.445.pdf
  • Filesize: 437 kB
  • 12 pages

Document Identifiers

Author Details

Debasis Mandal
A. Pavan
Rajeswari Venugopalan

Cite As Get BibTex

Debasis Mandal, A. Pavan, and Rajeswari Venugopalan. Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 445-456, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.FSTTCS.2014.445

Abstract

We show that there is a language that is Turing complete for NP but not many-one complete for NP, under a worst-case hardness hypothesis. Our hypothesis asserts the existence of a non-deterministic, double-exponential time machine that runs in time O(2^2^n^c) (for some c > 1) accepting Sigma^* whose accepting computations cannot be computed by bounded-error, probabilistic machines running in time O(2^2^{beta * 2^n^c) (for some beta > 0). This is the first result that separates completeness notions for NP under a worst-case hardness hypothesis.

Subject Classification

Keywords
  • Cook reduction
  • Karp reduction
  • NP-completeness
  • Turing completeness
  • many-one completeness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Aida, R. Schuler, T. Tsukiji, and O. Watanabe. On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems. In 18th International Symposium on Theoretical Aspects of Computer Science, 2001. Google Scholar
  2. K. Ambos-Spies and L. Bentzien. Separating NP-completeness under strong hypotheses. Journal of Computer and System Sciences, 61(3):335-361, 2000. Google Scholar
  3. S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Google Scholar
  4. L. Babai and S. Laplante. Stronger separations ofor random-self-reducibility, rounds, and advice. In 14th IEEE Conference on Computational Complexity, pages 98-104, 1999. Google Scholar
  5. H. Buhrman, S. Homer, and L. Torenvliet. Completeness notions for nondeterministic complexity classes. Mathematical Systems Theory, 24:179-200, 1991. Google Scholar
  6. H. Buhrman and L. Torenvliet. On the structure of complete sets. In 9th IEEE Annual Conference on Structure in Complexity Theory, pages 118-133, 1994. Google Scholar
  7. S. Cook. The complexity of theorem-proving procedures. In Proceedings of the 3rd ACM Symposium on Theory of Computing, pages 151-158, 1971. Google Scholar
  8. J. Feigenbaum, L. Fortnow, C. Lund, and D. Spielman. The power of adaptiveness and additional queries in random-self-reductions. In Proc. 7th Annual Conference on Structure in Complexity Theory, pages 338-346, 1992. Google Scholar
  9. J. Feigenbaun, L. Fortnow, S. Laplante, and A. Naik. On coherence, random-self-reducibility, and self-correction. In Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, pages 224-232, 1996. Google Scholar
  10. X. Gu, J. Hitchcock, and A. Pavan. Collapsing and separating completeness notions under average-case and worst-case hypotheses. Theory of Computing Systems, 51(2):248-265, 2011. Google Scholar
  11. E. Hemaspaandra, A. Naik, M. Ogiwara, and A. Selman. P-selective sets and reducing search to decision vs. self-reducibility. Journal of Computer and System Sciences, 53(2):194-209, 1996. Google Scholar
  12. J. Hitchcock and A. Pavan. Hardness hypotheses, derandomization, and circuit complexity. Computational Complexity, 17(1):119-146, 2008. Google Scholar
  13. J. Hitchcock, A. Pavan, and N. V. Vinodchandran. Partial bi-immunity, scaled dimension and np-completeness. Theory of Computing Systems, 42(2):131-142, 2008. Google Scholar
  14. S. Homer. Structural properties of complete problems for exponential time. In L. Hemaspaandra and A. Selman, editors, Complexity Theory Retrospective II, pages 135-153. Springer-Verlag, 1997. Google Scholar
  15. D. W. Juedes and J. H. Lutz. The complexity and distribution of hard problems. SIAM Joutnal on Computing, 24:279-295, 1995. Google Scholar
  16. R. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85-104. Plenum Press, New York, 1972. Google Scholar
  17. K. Ko and D. Moore. Completeness, approximation and density. SIAM Journal on Computing, 10(4):787-796, Nov. 1981. Google Scholar
  18. R. Ladner, N. Lynch, and A. Selman. A comparison of polynomial time reducibilities. Theoretical Computer Science, 1:103-123, 1975. Google Scholar
  19. L. Levin. Universal sorting problems. Problems of Information Transmission, 9:265-266, 1973. English translation of original in Problemy Peredaci Informacii. Google Scholar
  20. J. H. Lutz and E. Mayordomo. Cook versus Karp-Levin: Separating completeness notions if NP is not small. Theoretical Computer Science, 164:141-163, 1996. Google Scholar
  21. A. Pavan and A. Selman. Separation of NP-completeness notions. SIAM Journal on Computing, 31(3):906-918, 2002. Google Scholar
  22. A. Pavan and A. Selman. Bi-immunity separates strong NP-completeness notions. Information and Computation, 188:116-126, 2004. Google Scholar
  23. A. Selman. P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. Mathematical Systems Theory, 13:55-65, 1979. Google Scholar
  24. S. Tang, B. Fu, and T. Liu. Exponential time and subexponential time sets. Theoretical Computer Science, 115(2):371-381, 1993. Google Scholar
  25. S. Toda. On polynomial-time truth-table reducibilities of intractable sets to P-selective sets. Mathematical Systems Theory, 24(2):69-82, 1991. Google Scholar
  26. L. Valiant and V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47:85-93, 1986. Google Scholar
  27. O. Watanabe. A comparison of polynomial time completeness notions. Theoretical Computer Science, 54:249-265, 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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