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: V. Arvind , Y. Han , L. Hemachandra , J. Köbler , A. Lozano , M. Mundhenk , M. Ogiwara , U. Schöning , R. Silvestri , T. Thierauf, Reductions to sets of low information content, Complexity theory: current research, Cambridge University Press, New York, NY, 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: Harry Buhrman , Lance Fortnow , Leen Torenvliet, Six Hypotheses in Search of a Theorem, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, p.2, June 24-27, 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: Jin-Yi Cai , Mitsunori Ogihara, Sparse sets versus complexity classes, Complexity theory retrospective II, Springer-Verlag New York, Inc., New York, NY, 1998
• 7: Lane A. Hemaspaandra , Christian Glaßer, A moment of perfect clarity I: the parallel census technique, ACM SIGACT News, v.31 n.3, p.37-42, Sept. 2000 [doi>10.1145/356458.356459]
• 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: Johannes Köbler , Osamu Watanabe, New Collapse Consequences of NP Having Small Circuits, SIAM Journal on Computing, v.28 n.1, p.311-324, Feb. 1999 [doi>10.1137/S0097539795296206]
• 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: Mitsunori Ogiwara , Osamu Watanabe, On polynomial-time bounded truth-table reducibility of NP sets to sparse sets, SIAM Journal on Computing, v.20 n.3, p.471-483, June 1991 [doi>10.1137/0220030]
• 16: [Siv00] D. Sivakumar, May 6, 2000. Personal Communication.
• 17: [vM97] D. van Melkebeek, 1997. Personal Communication.
• 18: L. G. Valiant , V. V. Vazirani, NP is as easy as detecting unique solutions, Theoretical Computer Science, v.47 n.1, p.85-93, Nov. 1986
• 19: Paul Young, How reductions to sparse sets collapse the polynomial-time hierarchy: a primer; part I: polynomial-time Turing reductions, ACM SIGACT News, v.23 n.3, p.107-117, Summer 1992 [doi>10.1145/141914.141921]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Set theory

General Terms:
Algorithms, Theory, Verification