## [Computational Complexity] Sparse Sets (Tribute to Mahaney)

Expand Messages
• For more information on Steve Mahaney s untimely demise see here. Mahaney s theorem is If there is a set S that is both sparse and NP complete then P=NP Lance
Message 1 of 1 , Jun 29, 2007

Mahaney's theorem is
If there is a set S that is both sparse and NP complete then P=NP
Lance has already done a nice blog entry on this topic, so I will take this in a different direction.

I looked in Joel Seifras's theroy database for theory articles with the word `sparse' in them. I then edited it down to articles that relate directly or indirectly to Mahaney's theorem. While this is hard to make precise, there were over 100 articles that owe a debt of gratitude to Mahaney's papers (I do not know how many of them cited Mahaney's paper.)

I list the articles that seem most directly related to Mahaney's paper. I may have left out papers that ended up being superseded by papers on this list.

1. If there is a sparse S that is NP-complete then P=NP. Sparse Complete Sets for NP: Solution of a Conjecture of Berman and Hartmanis, by Mahaney. 1982 JCSS, Vol 25. (earlier version in FOCS 1980, 25th FOCS)
2. If there is a sparse S that is NP-hard under btt-reductions then P=NP. On Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets, SICOMP 1991, V. 20 by Ogiwara and Watanabe (earlier version in STOC 1990, 22 STOC)
3. An easier proof of Ogiwara-Watnabe paper with better bounds: On Reductions of NP Sets to Sparse Sets by Homer and Longpre. JCSS 1994, V. 48 (Earlier version in COMPLEXITY 1991)
4. Generalize to counting classes. For example, if there is a set that is btt-hard for MOD2P then MOD2P=P On Sparse Hard Sets for Counting Classes. by Ogiwara and Lozano, TCS 1993, V. 112.
5. If there is a sparse set that is NP-hard under Turing reductions then PH=\Sigma2p Some Connections Between Nonuniform and Uniform Complexity Classes, by Karp and Lipton, STOC 1982
6. If there is a sparse set that is NP-hard under Turing reductions then PH collapse further. (Complicated to state exactly how much further). Competing Provers Yield Improved Karp-Lipton Collapse Results, by Cai and Chakaravarthy and Hemaspaandra and Ogihara, INFCTRL, 2005, V. 198
7. If there is a sparse set complete for P under log-space many-one reductions then P=L. Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis, by Cai and Sivakumar, JCSS 1999, V. 58. (Earlier version in COCOON 1997)

--
Posted By GASARCH to Computational Complexity at 6/29/2007 04:23:00 PM
Your message has been successfully submitted and would be delivered to recipients shortly.