Computational Complexity

Friday, June 29, 2007

 
Sparse Sets (Tribute to Mahaney)

Posted by GASARCH

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 MOD₂P then MOD₂P=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=\Sigma₂^p 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)

4:23 PM #

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

   5:18 PM, June 29, 2007

2.  Anonymous says:  
   
   What is Joel Seifras's theory database?
   

   3:23 AM, July 01, 2007

3.  Anonymous says:  
   
   Small sets
   

   5:28 AM, July 01, 2007

4.  GASARCH says:  
   
   Joel Seifras theory database is one line for
   every 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
   

   11:02 AM, July 02, 2007