A moment of perfect clarity II: consequences of sparse sets hard for NP with respect to weak reductions

Abstract

This issue's column, Part II of the article started in the preceding issue, is about progress on the question of whether NP has sparse hard sets with respect to weak reductions.Upcoming Complexity Theory Column articles include A. Werschulz on information-based complexity; J. Castro, R. Gavaldà, and D. Guijarro on what complexity theorists can learn from learning theory; S. Ravi Kumar and D. Sivakumar on a to-be-announced topic; M. Holzer and P. McKenzie on alternating stack machines; and R. Paturi on the complexity of k-SAT.

References

1. {AHH⁺93} V. Arvind, Y. Han, L. Hemachandra, J. Köbler, A. Lozano, M. Mundhenk, M. Ogiwara, U. Schöning, R. Silvestri, and T. Thierauf. Reductions to sets of low information content. In K. Ambos-Spies, S. Homer, and U. Schöning, editors, Complexity Theory, pages 1-45. Cambridge University Press, 1993.
2. {AKM96} V. Arvind, J. Köbler, and M. Mundhenk. Upper bounds for the complexity of sparse and tally descriptions. Mathematical Systems Theory, 29:63-94, 1996.
3. {BFT97} H. Buhrman, L. Fortnow, aud L. Torenvliet. Six hypotheses in search of a theorem. In Proceedings of the 12th Annual IEEE Conference on Computational Complexity, pages 2-12. IEEE Comptuer Society Press, 1997.
4. {CHW99} J. Cai, L. Hemaspaandra, and G. Wechsung. Robust reductions. Theory of Computing Systems, 32(6):625-647, 1999.
5. {CNS95} J. Cai, A. Naik, and D. Sivakumar. On the existence of hard sparse sets under weak reductions. Technical Report 95-31, Department of Computer Science, State University of New York at Buffalo, Buffalo, NY, July 1995.
6. {CO97} J. Cai and M. Ogihara. Sparse sets versus complexity classes. In L. Hemaspaandra and A. Selman, editors, Complexity Theory Retrospective II, pages 53-80. Springer-Verlag, 1997.
7. {GH00} C. Glaßer and L. Hemaspaandra. A moment of perfect clarity I: The parallel census technique. SIGACT News, 31(3):37-42, 2000.
8. {Gla00} C. Glaßer. Consequences of the existence of sparse sets hard for NP under a subclass of truth-table reductions. Technical Report TR 245, Institut für Informatik, Universität Würzburg, Würzburg, Germany, January 2000.
9. {HOW92} L. Hemachandra, M. Ogiwara, and O. Watanabe. How hard are sparse sets? In Proceedings of the 7th Structure in Complexity Theory Conference, pages 222-238. IEEE Computer Society Press, June 1992.
10. {Kad89} J. Kadin. p^{NP{log n}} and sparse Turing-complete sets for NP. Journal of Computer and System Sciences, 39(3):282-298, 1989.
11. {KW99} J. Köbler and O. Watanabe. New collapse consequences of NP having small circuits. SIAM Journal on Computing, 28(1):311-324, 1999.
12. {LLS75} R. Ladner, N. Lynch, and A. Selman. A comparison of polynomial time reducibilities. Theoretical Computer Science, 1(2):103-124, 1975.
13. {Mah82} S. Mahaney. Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis. Journal of Computer and System Sciences, 25(2):130-143, 1982.
14. {Mah86} S. Mahaney. Sparse sets and reducibilities. In R. Book, editor, Studies in Complexity Theory, pages 63-118. John Wiley and Sons, 1986.
15. {OW91} M. Ogiwara and O. Watanabe. On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing, 20(3):471-483, June 1991.
16. {Siv00} D. Sivakumar, May 6, 2000. Personal Communication.
17. {vM97} D. van Melkebeek, 1997. Personal Communication.
18. {VV86} L. Valiant and V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47:85-93, 1986.
19. {You92} P. Young. How reductions to sparse sets collapse the polynomial-time hierarchy: A primer. SIGACT News, 1992. Part I (#3, pages 107-117), Part II (#4, pages 83-94), and Corrigendum to Part I (#4, page 94).

Index Terms

• Mathematics of computing

  • Discrete mathematics

• Theory of computation

  • Computational complexity and cryptography

    • Complexity classes

  • Logic

    • Type theory