Linguagem esparsa: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Dianakc moveu Linguagem Esparça para Linguagem esparsa |
correção |
||
Linha 1:
Em [[teoria da complexidade computacional]], uma '''linguagem esparsa''' é uma [[linguagem formal]] (um conjunto de ''[[string]]s'') 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 (complexidade) | NP]] com outras classes. A [[classe de complexidade]] de todas as línguas
As linguagens esparsas são chamados de "esparsas", porque há um total de 2<sup>''n''</sup> ''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 [[linguagem unária|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 [[Coeficiente binomial|<math>\binom{n}{k}</math>]] ''strings'' na linguagem, que é delimitada por ''n''<sup>''k''</sup>.
| |||