This HTML5 document contains 61 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n15http://weblog.fortnow.com/2007/06/
dcthttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n18https://global.dbpedia.org/id/
dbpedia-hehttp://he.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
n14http://weblog.fortnow.com/2006/04/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
dbpedia-zhhttp://zh.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
dbphttp://dbpedia.org/property/
xsdhhttp://www.w3.org/2001/XMLSchema#
n5http://dbpedia.org/resource/P/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Sparse_language
rdf:type
yago:Language106282651 yago:WikicatFormalLanguages yago:Communication100033020 yago:Abstraction100002137
rdfs:label
Langage creux Linguagem esparsa 稀疏語言 Sparse language
rdfs:comment
在計算複雜性理論裡面, 稀疏語言是一種形式語言 (一堆字串的集合字串)，並且這語言內長度為n的字串個數，被一個n的多項式所限制住。 這種語言主要被用來研究NP這類語言與其他種類語言的關係。包含所有稀疏語言的複雜度類被稱作SPARSE。 稀疏語言會被叫做稀疏的原因是因為，對任何語言，長度為n的字串可能性個數總共有2n個，而如果某特定語言只有包含這一些字串裡面的多項式個數個，那這語言所包含字串的比例會隨著n的成長很快的減少。 所有一元語言都是稀疏語言。一個稀疏語言比較不單純的例子是，某個語言包含所有恰有k個1(k是某個常數)的二進位字串，; 對任何長度n, 這個語言僅包含個字串, 而這個數字則被 nk給限制住。 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. 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 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.
dct:subject
dbc:Computational_complexity_theory dbc:Formal_languages
dbo:wikiPageID
12769596
dbo:wikiPageRevisionID
1118453397
dbo:wikiPageWikiLink
dbr:Polynomial-time_Turing_reduction n5:poly dbr:Karp_reduction dbr:NP-complete dbr:NP-hard dbc:Computational_complexity_theory dbr:Mahaney's_theorem dbr:Unary_language dbr:Turing_reduction dbr:NE_(complexity) dbr:Complexity_class dbr:Complexity_function dbr:Polynomial dbr:Formal_language dbr:L_(complexity) dbr:E_(complexity) dbr:Binomial_coefficient dbr:P-complete dbr:String_(computer_science) dbc:Formal_languages dbr:P_(complexity) dbr:William_Gasarch dbr:Lance_Fortnow dbr:Co-NP-complete dbr:Computational_complexity_theory dbr:P_=_NP_problem dbr:NP_(complexity)
dbo:wikiPageExternalLink
n14:favorite-theorems-small-sets.html n15:sparse-sets-tribute-to-mahaney.html
owl:sameAs
freebase:m.02x442d dbpedia-he:שפה_דלילה dbpedia-fr:Langage_creux n18:4vd88 dbpedia-zh:稀疏語言 wikidata:Q7573802 dbpedia-pt:Linguagem_esparsa yago-res:Sparse_language
dbp:wikiPageUsesTemplate
dbt:CZoo
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. 在計算複雜性理論裡面, 稀疏語言是一種形式語言 (一堆字串的集合字串)，並且這語言內長度為n的字串個數，被一個n的多項式所限制住。 這種語言主要被用來研究NP這類語言與其他種類語言的關係。包含所有稀疏語言的複雜度類被稱作SPARSE。 稀疏語言會被叫做稀疏的原因是因為，對任何語言，長度為n的字串可能性個數總共有2n個，而如果某特定語言只有包含這一些字串裡面的多項式個數個，那這語言所包含字串的比例會隨著n的成長很快的減少。 所有一元語言都是稀疏語言。一個稀疏語言比較不單純的例子是，某個語言包含所有恰有k個1(k是某個常數)的二進位字串，; 對任何長度n, 這個語言僅包含個字串, 而這個數字則被 nk給限制住。 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. 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.
prov:wasDerivedFrom
wikipedia-en:Sparse_language?oldid=1118453397&ns=0
dbo:wikiPageLength
4553
foaf:isPrimaryTopicOf
wikipedia-en:Sparse_language