Friday, June 29, 2007

Sparse Sets (Tribute to Mahaney)

For more information on Steve Mahaney's untimely demise see here and here is how you can contribute to help honor his memory.

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)


  1. "Sparse Complete Sets for NP: Solution of a Conjecture of Berman and Hartmanis" has 119 citations on Google Scholar.

  2. What is Joel Seifras's theory database?

  3. Joel Seifras theory database is one line for
    every paper EVERY published
    in theory. goto

    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?