Notação L

​A notação L é uma notação assintótica análoga à notação O grande, denotada como ${\displaystyle L_{n}[\alpha ,c]}$ para uma variável limitada ${\displaystyle n}$ tendendo ao infinito. Como a notação O grande, geralmente é usada para transmitir aproximadamente a complexidade computacional de um algoritmo específico.

Definição

Ela está definida como

${\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$ onde c é uma constante positiva e ${\displaystyle \alpha }$ é uma constante ${\displaystyle 0\leq \alpha \leq 1}$.

A notação L é usada principalmente na teoria computacional dos números, para expressar a complexidade de algoritmos para problemas difíceis da teoria dos números, por ex. peneiras para fatoração de inteiros e métodos para resolver logaritmos discretos. O benefício dessa notação é que ela simplifica a análise desses algoritmos.

${\displaystyle e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$ expressa o termo dominante, e ${\displaystyle e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$ cuida de tudo menor.

Quando ${\displaystyle \alpha }$ ​0, então

${\displaystyle L_{n}[\alpha ,c]=L_{n}[0,c]=e^{(c+o(1))\ln \ln n}=(\ln n)^{c+o(1)}\,}$

é uma função polinomial de ln n;

Quando ${\displaystyle \alpha }$ é 1, então

${\displaystyle L_{n}[\alpha ,c]=L_{n}[1,c]=e^{(c+o(1))\ln n}=n^{c+o(1)}\,}$

é uma função totalmente exponencial de ln n (e, portanto, polinomial em n).

Se ${\displaystyle \alpha }$ estiver entre 0 e 1, a função é subexponencial de ln n (e superpolinomial).

Exemplos

Muitos algoritmos de fatoração de inteiros de propósito geral têm complexidades temporais subexponenciais. O melhor é a peneira de campo de número geral, que tem um tempo de execução esperado de

${\displaystyle L_{n}[1/3,c]=e^{(c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}}}$

para ${\displaystyle c=(64/9)^{1/3}\approx 1,923}$. O melhor algoritmo antes da peneira de campo numérico era a peneira quadrática que tem tempo de execução

${\displaystyle L_{n}[1/2,1]=e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,}$

Para o problema de logaritmo discreto de curva elíptica, o algoritmo de propósito geral mais rápido é o algoritmo passo de bebê passo gigante, que tem um tempo de execução na ordem da raiz quadrada da ordem n. Em notação L, isso seria

${\displaystyle L_{n}[1,1/2]=n^{1/2+o(1)}.\,}$

A existência do teste de primalidade AKS, que é executado em tempo polinomial, significa que a complexidade de tempo para o teste de primalidade é conhecida como sendo no máximo

${\displaystyle L_{n}[0,c]=(\ln n)^{c+o(1)}\,}$

onde c foi provado ser no máximo 6.^[1]

História

A notação L foi definida de várias formas na literatura. O primeiro uso dela veio de Carl Pomerance em seu artigo "Análise e comparação de alguns algoritmos de fatoração de inteiros".^[2] Esta forma tinha apenas o parâmetro ${\displaystyle c}$: o ${\displaystyle \alpha }$ na fórmula era ${\displaystyle 1/2}$ para os algoritmos que ele estava analisando. Pomerance estava usando a letra ${\displaystyle L}$ (ou minúscula ${\displaystyle l}$) neste trabalho e em trabalhos anteriores para fórmulas que envolviam muitos logaritmos.

A fórmula acima envolvendo dois parâmetros foi introduzida por Arjen Lenstra e Hendrik Lenstra em seu artigo sobre "algoritmos na teoria dos números".^[3] Foi introduzido na análise de um algoritmo de logaritmo discreto de Coppersmith. Esta é a forma mais comumente usada na literatura hoje.

O manual de criptografia aplicada define a notação L com um ${\displaystyle O}$ grande em torno da fórmula apresentada neste artigo.^[4] Esta não é a definição padrão. O ${\displaystyle O}$ grande sugere que o tempo de execução é um limite superior. No entanto, para os algoritmos de fatoração de inteiros e logaritmos discretos para os quais a notação L é comumente usada, o tempo de execução não é um limite superior, portanto, essa definição não é preferida.

Referências