Notazione L

La notazione L è una notazione asintotica analoga alla notazione O-grande, denotata come L n [ α , c ] {\displaystyle L_{n}[\alpha ,c]} per una variabile limitata n {\displaystyle n} tendente a infinito. Come la notazione O-grande, è usata di solito per rendere in maniera approssimativa la complessità computazionale di un particolare algoritmo.

Essa è definita come

L n [ α , c ] = e ( c + o ( 1 ) ) ( ln ⁡ n ) α ( ln ⁡ ln ⁡ n ) 1 − α , {\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }},}

dove c è una costante positiva, e α {\displaystyle \alpha } è una costante 0 ≤ α ≤ 1 {\displaystyle 0\leq \alpha \leq 1} .

La notazione L si usa principalmente nella teoria computazionale dei numeri, per esprimere la complessità degli algoritmi per i problemi difficili della teoria dei numeri, ad es. per la fattorizzazione degli interi e per i metodi di soluzione dei logaritmi discreti. Il beneficio di questa notazione è che semplifica l'analisi di questi logaritmi. La e c ( ln ⁡ n ) α ( ln ⁡ ln ⁡ n ) 1 − α {\displaystyle e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}} esprime il termine dominante, e la e o ( 1 ) ( ln ⁡ n ) α ( ln ⁡ ln ⁡ n ) 1 − α {\displaystyle e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}} copre tutto ciò che è minore.

Quando α {\displaystyle \alpha } è 0, allora

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

è una funzione polinomiale di ln n; quando α {\displaystyle \alpha } è 1, allora

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

è una funzione completamente esponenziale di ln n (e quindi polinomiale in n).

Se α {\displaystyle \alpha } è compreso tra 0 e 1, la funzione è subesponenziale (e superpolinomiale).

Esempi

Molti algoritmi multiuso di fattorizzazione degli interi hanno complessità temporali subesponenziali. Il migliore è il crivello dei campi di numeri generale, che ha un tempo di esecuzione stimato di

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

per c = ( 64 / 9 ) 1 / 3 {\displaystyle c=(64/9)^{1/3}} . Il migliore di tali algoritmi anteriormente al crivello dei campi di numeri era il crivello quadratico, che ha tempo di esecuzione

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

Per il problema del logaritmo discreto delle curve ellittiche, il più veloce algoritmo multiuso è l'algoritmo baby-step giant-step. che ha un tempo di esecuzione sull'ordine della radice quadrata dell'ordine del gruppo n. Nella notazione L questo sarebbe

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

L'esistenza del test di primalità AKS, che funziona in tempo polinomiale, significa che è noto che la complessità temporale per i test di primalità è al massimo

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

dove si è provato che c è al massimo 6.[1]

Storia

La notazione L è stata definita in varie forme nella letteratura. Il primo uso venne da Carl Pomerance nel suo scritto "Analysis and comparison of some integer factoring algorithms".[2] Questa forma aveva soltanto il parametro c {\displaystyle c} : l' α {\displaystyle \alpha } nella formula era 1 / 2 {\displaystyle 1/2} per gli algoritmi che egli stava analizzando. Pomerance aveva usato la lettera L {\displaystyle L} (o la minuscola l {\displaystyle l} ) in questo e in precedenti studi per formule che coinvolgevano molti logaritmi.

La suddetta formula con due parametri fu introdotta da Arjen Lenstra ed Hendrik Lenstra nel loro articolo su "Algorithms in Number Theory".[3] Fu introdotta nella loro analisi di un algoritmo di logaritmi discreti di Coppersmith. Questa è la forma usata più comuneme in letteratura oggi.

Lo Handbook of Applied Cryptography definisce la notazione L con una O {\displaystyle O} grande intorno alla formula presentata in questo articolo.[4] Questa non è la definizione normale. La O {\displaystyle O} grande suggerirebbe che il tempo di esecuzione è un limite superiore. Tuttavia, per gli algoritmi di fattorizzazione degli interi e di logaritmi discreti per i quali si usa comunemente la notazione L, il empo di esecuzione non è un limite superiore, perciò questa definizione non è quella preferita.

Note

  1. ^ Hendirk W. Lenstra Jr. e Carl Pomerance, "Primality testing with Gaussian periods" Archiviato il 25 febbraio 2012 in Internet Archive., prestampa, 2011.
  2. ^ Carl Pomerance, "Analysis and comparison of some integer factoring algorithms", in Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982.
  3. ^ Arjen K. Lenstra e Hendrik W. Lenstra, Jr, "Algorithms in Number Theory", in Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1991.
  4. ^ Alfred J. Menezes, Paul C. van Oorschot e Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996. ISBN 0-8493-8523-7.

Voci correlate

  Portale Informatica
  Portale Matematica