About: Sparse language

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Type of formal language in computational complexity theory

Property	Value
dbo:description	type of formal language in computational complexity theory (en)
dbo:wikiPageExternalLink	http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html http://weblog.fortnow.com/2007/06/sparse-sets-tribute-to-mahaney.html
dbo:wikiPageWikiLink	dbr:Co-NP-complete dbr:NP_(complexity) dbr:Binomial_coefficient dbr:E_(complexity) dbr:NE_(complexity) dbc:Computational_complexity_theory dbr:Formal_language dbr:L_(complexity) dbc:Formal_languages dbr:Lance_Fortnow dbr:Computational_complexity_theory dbr:Polynomial dbr:Complexity_class dbr:P-complete dbr:Unary_language dbr:P_(complexity) dbr:Turing_reduction dbr:P/poly dbr:String_(computer_science) dbr:Complexity_function dbr:William_Gasarch dbr:NP-complete dbr:NP-hard dbr:Mahaney's_theorem dbr:P_=_NP_problem dbr:Karp_reduction dbr:Polynomial-time_Turing_reduction
dbp:wikiPageUsesTemplate	dbt:CZoo
dct:subject	dbc:Computational_complexity_theory dbc:Formal_languages
rdfs:label	Sparse language (en) Langage creux (fr) Linguagem esparsa (pt) 稀疏語言 (zh)
owl:sameAs	freebase:Sparse language yago-res:Sparse language wikidata:Sparse language dbpedia-fr:Sparse language dbpedia-zh:Sparse language dbpedia-pt:Sparse language dbpedia-he:Sparse language dbpedia-global:Sparse language
prov:wasDerivedFrom	wikipedia-en:Sparse_language?oldid=1205289569&ns=0
foaf:isPrimaryTopicOf	wikipedia-en:Sparse_language
is dbo:wikiPageDisambiguates of	dbr:Sparse_(disambiguation)
is dbo:wikiPageRedirects of	dbr:Sparse_set
is dbo:wikiPageWikiLink of	dbr:Co-NP-complete dbr:Sparse_(disambiguation) dbr:NEXPTIME dbr:EXPTIME dbr:Berman–Hartmanis_conjecture dbr:Juris_Hartmanis dbr:Lance_Fortnow dbr:P-complete dbr:Unary_language dbr:P_(complexity) dbr:P/poly dbr:Complexity_function dbr:Mahaney's_theorem dbr:Sparse_set
is foaf:primaryTopic of	wikipedia-en:Sparse_language