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 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.