Linguagem esparsa: diferenças entre revisões
m Dianakc moveu Linguagem Esparça para Linguagem esparsa |
correção |
||
| Linha 1: | 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 |
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 esparsas são chamadas de SPARSE. |
||
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>. |
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>. |
||
Revisão das 11h29min de 18 de novembro de 2014
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.
Relacionamentos com outras classes de complexidade
SPARSE contém TALLY, a classe de línguagem unária, uma vez que estas têm no máximo uma sequência de qualquer comprimento. Embora nem todas as linguagens em P/polinomial sejam esparsas, existe uma Redução em tempo polinomial de cada linguagem em P/poly para linguagens esparsas.[1] Fortune mostrou em 1979 que, se qualquer linguagem esparsa é co-NP-completo, então P = NP;[2] Mahaney usou isso para mostrar em 1982 que, se qualquer linguagem esparsa é NP-completo, então P = NP (este é o Teorema de Mahaney).[3] Uma prova mais simples baseado desta conjuntos de esquerda foi dada por Ogihara e Osamu em 1991.[4] E ≠ NE se e somente se existem linguagens esparsas em NP que não estão em P.[5] Em 1999, Jin-Yi Cai e D. Sivakumar, construindo sobre o trabalho de Ogihara, mostraram que, se existe um problema esparso de P-completo, entãoL = P.[6]
Referências
- ↑ Jin-Yi Cai. Lecture 11: P=poly, Sparse Sets, and Mahaney's Theorem. CS 810: Introduction to Complexity Theory. The University of Wisconsin–Madison. September 18, 2003. http://www.wisdom.weizmann.ac.il/~oded/CC/mahaney.pdf
- ↑ S. Fortune. A note on sparse complete sets. SIAM Journal on Computing, volume 8, issue 3, pp.431–433. 1979.
- ↑ S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. Journal of Computer and System Sciences 25:130-143. 1982.
- ↑ M. Ogiwara and O. Watanabe. On polynomial time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing volume 20, pp.471–483. 1991.
- ↑ Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, volume 65, issue 2/3, pp.158–181. 1985. At ACM Digital Library
- ↑ Jin-Yi Cai and D. Sivakumar. Sparse hard sets for P: resolution of a conjecture of Hartmanis. Journal of Computer and System Sciences, volume 58, issue 2, pp.280–296. 1999. ISSN:0022-0000. At Citeseer