| dbo:abstract
|
- En théorie de la complexité, un langage creux est un langage où le nombre de mots de longueur n est borné par un polynôme en n. Ils sont utiles dans l'étude de la classe NP. L'adjectif creux illustre bien un tel langage : sur un alphabet à deux lettres, comme il y a 2 n mots de longueur n, alors s'il n'y a qu'un nombre polynomial de mots de longueur n, cela signifie que la proportion de mots de longueur n dans un langage creux tend vers 0, quand n tend vers l'infini. (fr)
- 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. (en)
- Em teoria da complexidade computacional, uma linguagem esparsa é uma linguagem formal (um conjunto de strings) cujo número de strings de comprimento n na língua é limitada por uma função de polinômio n. São utilizadas principalmente no estudo da relação entre a classe de complexidade NP com outras classes. A classe de complexidade de todas as línguas esparsas são chamadas de SPARSE. As linguagens esparsas são chamados de "esparsas", porque há um total de 2n strings de comprimento n, e se uma linguagem só contém polinomialmente muitos destes, então a proporção de cadeias de comprimento n que contém rapidamente vai de zero quanto a medida que n crescer. Todos linguagens unárias são esparsas. Um exemplo de uma linguagem esparsa não trivial é o conjunto de cadeias binárias contendo exatamente k 1 bits para alguns k fixos; para cada n, há apenas strings na linguagem, que é delimitada por nk. (pt)
- 在計算複雜性理論裡面, 稀疏語言是一種形式語言 (一堆字串的集合字串)，並且這語言內長度為n的字串個數，被一個n的多項式所限制住。 這種語言主要被用來研究NP這類語言與其他種類語言的關係。包含所有稀疏語言的複雜度類被稱作SPARSE。 稀疏語言會被叫做稀疏的原因是因為，對任何語言，長度為n的字串可能性個數總共有2n個，而如果某特定語言只有包含這一些字串裡面的多項式個數個，那這語言所包含字串的比例會隨著n的成長很快的減少。 所有一元語言都是稀疏語言。一個稀疏語言比較不單純的例子是，某個語言包含所有恰有k個1(k是某個常數)的二進位字串，; 對任何長度n, 這個語言僅包含個字串, 而這個數字則被 nk給限制住。 (zh)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 4553 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En théorie de la complexité, un langage creux est un langage où le nombre de mots de longueur n est borné par un polynôme en n. Ils sont utiles dans l'étude de la classe NP. L'adjectif creux illustre bien un tel langage : sur un alphabet à deux lettres, comme il y a 2 n mots de longueur n, alors s'il n'y a qu'un nombre polynomial de mots de longueur n, cela signifie que la proportion de mots de longueur n dans un langage creux tend vers 0, quand n tend vers l'infini. (fr)
- 在計算複雜性理論裡面, 稀疏語言是一種形式語言 (一堆字串的集合字串)，並且這語言內長度為n的字串個數，被一個n的多項式所限制住。 這種語言主要被用來研究NP這類語言與其他種類語言的關係。包含所有稀疏語言的複雜度類被稱作SPARSE。 稀疏語言會被叫做稀疏的原因是因為，對任何語言，長度為n的字串可能性個數總共有2n個，而如果某特定語言只有包含這一些字串裡面的多項式個數個，那這語言所包含字串的比例會隨著n的成長很快的減少。 所有一元語言都是稀疏語言。一個稀疏語言比較不單純的例子是，某個語言包含所有恰有k個1(k是某個常數)的二進位字串，; 對任何長度n, 這個語言僅包含個字串, 而這個數字則被 nk給限制住。 (zh)
- 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. (en)
- Em teoria da complexidade computacional, uma linguagem esparsa é uma linguagem formal (um conjunto de strings) cujo número de strings de comprimento n na língua é limitada por uma função de polinômio n. São utilizadas principalmente no estudo da relação entre a classe de complexidade NP com outras classes. A classe de complexidade de todas as línguas esparsas são chamadas de SPARSE. (pt)
|
| rdfs:label
|
- Langage creux (fr)
- Sparse language (en)
- Linguagem esparsa (pt)
- 稀疏語言 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
