Linguagem esparsa

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 2ⁿ 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 ${\binom {n}{k}}$ strings na linguagem, que é delimitada por n^k.

Relacionamentos com outras classes de complexidade

SPARSE contém TALLY, a classe de linguagem 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. Fortune mostrou em 1979 que, se qualquer linguagem esparsa é co-NP-completo, então P = NP; Mahaney usou isso para mostrar em 1982 que, se qualquer linguagem esparsa é NP-completo, então P = NP (este é o Teorema de Mahaney). Uma prova mais simples baseado desta conjuntos de esquerda foi dada por Ogihara e Osamu em 1991. E ≠ NE se e somente se existem linguagens esparsas em NP que não estão em P. 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.