Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Sparse_language> ?p ?o. }
Showing items 1 to 23 of
23
with 100 items per page.
- Sparse_language abstract "In computational complexity theory, a sparse language is a formal language (a set of strings) such that the complexity function, counting the number of strings of length n in the language, is bounded by a polynomial function of n. They are used primarily in the study of the relationship of the complexity class NP with other classes. The complexity class of all sparse languages is called SPARSE.Sparse languages are called sparse because there are a total of 2n strings of length n, and if a language only contains polynomially many of these, then the proportion of strings of length n that it contains rapidly goes to zero as n grows. All unary languages are sparse. An example of a nontrivial sparse language is the set of binary strings containing exactly k 1 bits for some fixed k; for each n, there are only strings in the language, which is bounded by nk.".
- Sparse_language wikiPageExternalLink favorite-theorems-small-sets.html.
- Sparse_language wikiPageExternalLink sparse-sets-tribute-to-mahaney.html.
- Sparse_language wikiPageID "12769596".
- Sparse_language wikiPageRevisionID "602111033".
- Sparse_language hasPhotoCollection Sparse_language.
- Sparse_language subject Category:Computational_complexity_theory.
- Sparse_language subject Category:Formal_languages.
- Sparse_language type Abstraction100002137.
- Sparse_language type Communication100033020.
- Sparse_language type FormalLanguages.
- Sparse_language type Language106282651.
- Sparse_language comment "In computational complexity theory, a sparse language is a formal language (a set of strings) such that the complexity function, counting the number of strings of length n in the language, is bounded by a polynomial function of n. They are used primarily in the study of the relationship of the complexity class NP with other classes.".
- Sparse_language label "Linguagem esparsa".
- Sparse_language label "Sparse language".
- Sparse_language label "稀疏語言".
- Sparse_language sameAs Linguagem_esparsa.
- Sparse_language sameAs m.02x442d.
- Sparse_language sameAs Q7573802.
- Sparse_language sameAs Q7573802.
- Sparse_language sameAs Sparse_language.
- Sparse_language wasDerivedFrom Sparse_language?oldid=602111033.
- Sparse_language isPrimaryTopicOf Sparse_language.