Sparse language

<h2 id="relationships-to-other-complexity-classes">Relationships to other complexity classes</h2>
<ul><li>SPARSE contains TALLY, the class of <a href="/facts/Unary_language/PgFd0PK1">unary languages</a>, since these have at most one string of any one length.</li></ul>
<ul><li>Although not all languages in <a href="/facts/P%2fpoly/cHXNlnYJ">P/poly</a> are sparse, there is a <a href="/facts/Polynomial-time_Turing_reduction/bBvfFxyM">polynomial-time Turing reduction</a> from any language in P/poly to a sparse language.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a></li>
<li>Fortune showed in 1979 that if any sparse language is <a href="/facts/Co-NP-complete/oGepXz5C">co-NP-complete</a>, then <a href="/facts/P_%253D_NP_problem/xoC7Ruda">P = NP</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> Mahaney used this to show in 1982 that if any sparse language is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>, then P = NP (this is <a href="/facts/Mahaney%2527s_theorem/cHosabn8">Mahaney's theorem</a>).<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> A simpler proof of this based on left-sets was given by Ogihara and Watanabe in 1991.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> Mahaney's argument does not actually require the sparse language to be in NP (because the existence of an NP-hard sparse set implies the existence of an NP-complete sparse set), so there is a sparse <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a> set if and only if P = NP.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a></li>
<li>Further, <a href="/facts/E_(complexity)/c3gskbGb">E</a> ≠ <a href="/facts/NE_(complexity)/PGxsCM70">NE</a> if and only if there exist sparse languages in NP that are not in P.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li>
<li>There is a <a href="/facts/Turing_reduction/qczcQTbz">Turing reduction</a> (as opposed to the <a href="/facts/Karp_reduction/bBvfFxyM">Karp reduction</a> from Mahaney's theorem) from an NP-complete language to a sparse language if and only if 
 
 
 
 
 
 NP
 
 
 ⊆
 
 
 P
 
 
 
 /
 
 
 poly
 
 
 
 {\displaystyle {\textbf {NP}}\subseteq {\textbf {P}}/{\text{poly}}}
 
.</li>
<li>In 1999, Jin-Yi Cai and D. Sivakumar, building on work by Ogihara, showed that if there exists a sparse <a href="/facts/P-complete/IX3sXDxl">P-complete</a> problem, then <a href="/facts/L_(complexity)/vCMV0edS">L</a> = <a href="/facts/P_(complexity)/2TYvck4k">P</a>.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="/facts/Lance_Fortnow/YlnwwT6G">Lance Fortnow</a>. <a href="http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html">Favorite Theorems: Small Sets</a>. April 18, 2006.</li>
<li><a href="/facts/William_Gasarch/JKVoUm4b">William Gasarch</a>. <a href="http://weblog.fortnow.com/2007/06/sparse-sets-tribute-to-mahaney.html">Sparse Sets (Tribute to Mahaney)</a>. June 29, 2007.</li>
<li><a href="/facts/Complexity_Zoo/htGK5zuz">Complexity Zoo</a>: <a href="https://complexityzoo.net/Complexity_Zoo:S#sparse">SPARSE</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Jin-Yi Cai. Lecture 11: P=poly, Sparse Sets, and Mahaney's Theorem. CS 810: Introduction to Complexity Theory. The University of Wisconsin–Madison. September 18, 2003 (PDF) <a href="http://www.wisdom.weizmann.ac.il/~oded/CC/mahaney.pdf" target="_blank">http://www.wisdom.weizmann.ac.il/~oded/CC/mahaney.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">S. Fortune. A note on sparse complete sets. SIAM Journal on Computing, volume 8, issue 3, pp.431–433. 1979. <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. Journal of Computer and System Sciences 25:130–143. 1982. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">M. Ogiwara and O. Watanabe. On polynomial time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing volume 20, pp.471–483. 1991. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim (1990). Structural Complexity II. Springer. pp. 130–131. ISBN 3-540-52079-1. <a href="3-540-52079-1" target="_blank">3-540-52079-1</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, volume 65, issue 2/3, pp.158–181. 1985. At ACM Digital Library <a href="http://portal.acm.org/citation.cfm?id=808769" target="_blank">http://portal.acm.org/citation.cfm?id=808769</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Jin-Yi Cai and D. Sivakumar. Sparse hard sets for P: resolution of a conjecture of Hartmanis. Journal of Computer and System Sciences, volume 58, issue 2, pp.280–296. 1999. ISSN 0022-0000. At Citeseer <a href="/wiki/ISSN_(identifier)" target="_blank">/wiki/ISSN_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
</ol>

Sparse language open-in-new

Sparse language