Mahaney's theorem is
If there is a set S that is both sparse and NP complete then P=NPLance 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.
- 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)
- 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)
- 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)
- Generalize to counting classes. For example, if there is a set that is btt-hard for MOD_{2}P then MOD_{2}P=P On Sparse Hard Sets for Counting Classes. by Ogiwara and Lozano, TCS 1993, V. 112.
- If there is a sparse set that is NP-hard under Turing reductions then PH=\Sigma_{2}^{p} Some Connections Between Nonuniform and Uniform Complexity Classes, by Karp and Lipton, STOC 1982
- 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
- 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)
"Sparse Complete Sets for NP: Solution of a Conjecture of Berman and Hartmanis" has 119 citations on Google Scholar.
ReplyDeleteWhat is Joel Seifras's theory database?
ReplyDeleteSmall sets
ReplyDeleteJoel Seifras theory database is one line for
ReplyDeleteevery paper EVERY published
in theory. goto
ftp://www.cs.rochester.edu/pub/u/joel
ALSO- anoymous 3, your link
to a post that my blog entry
also links to when I refer
to Lance's post on sparse
sets. I checked my link
and it was fine- so why
is your comment a link to it?
bill