Complessità temporale

In informatica, la complessità temporale di un algoritmo quantifica la quantità di tempo impiegata da un algoritmo a essere eseguito in funzione della lunghezza della stringa che rappresenta l'input^[1]^:226. La complessità temporale di un algoritmo è espressa comunemente usando la notazione O-grande, che esclude i coefficienti e i termini di ordine inferiore. Quando è espressa in questo modo, si dice che la complessità temporale è descritta asintoticamente, ossia, quando la dimensione degli input va a infinito. Ad esempio, se il tempo richiesto da un algoritmo su tutti gli input di dimensione n è al massimo 5n³ + 3n, la complessità temporale asintotica è O(n³).

La complessità temporale è stimata comunemente contando il numero di operazioni elementari eseguite dall'algoritmo, dove un'operazione elementare impiega una quantità di tempo fissa a essere eseguita. Così la quantità di tempo impiegata e il numero di operazioni elementari eseguite dall'algoritmo differiscono al massimo di un fattore costante.

Poiché il tempo di esecuzione di un algoritmo può variare con diversi input della stessa dimensione, si usa comunemente la complessità temporale del caso peggiore di un algoritmo, denotata come T(n), che è definita come la quantità di tempo massimo impiegata su qualsiasi input di dimensione n. Le complessità temporali sono classificate in base alla natura della funzione T(n). Ad esempio, un algoritmo con T(n) = O(n) è chiamato algoritmo in tempo lineare, e un algoritmo con T(n) = O(2ⁿ) si dice che è un algoritmo in tempo esponenziale.

Tabella di complessità temporali comuni

La tabella seguente sintetizza alcune classi di complessità temporali che si incontrano comunemente. Nella tabella, poly(x) = x^O(1), cioè, polinomiale in x.

Nome	Classe di complessità	Tempo di esecuzione (T(n))	Esempi di tempi di esecuzione	Algoritmi di esempio
tempo costante		O(1)	10	Determinare se un intero (rappresentato in binario) è pari o dispari
tempo inverso di Ackermann		O(α(n))		Tempo ammortizzato per un'operazione che usa un insieme disgiunto
tempo logaritmico iterato		O(log* n)		Colorazione distribuita di cicli
log-logaritmico		O(log log n)	Tempo ammortizzato per un'operazione che usa una coda di priorità vincolata^[2]
tempo logaritmico	DLOGTIME	O(log n)	log n, log(n²)	ricerca binaria
tempo polilogaritmico		poly(log n)	(log n)²
potenza frazionaria		O(n^c) dove 0 < c < 1	n^1/2, n^2/3	Ricerca in un albero kd
tempo lineare		O(n)	n	Trovare l'elemento più piccolo in un vettore non ordinato
tempo "n log asterisco n"		O(n log* n)		Algoritmo di triangolazione di un poligono di Seidel
tempo linearitmico		O(n log n)	n log n, log n!	Il più veloce ordinamento comparativo
tempo quadratico		O(n²)	n²	Ordinamento a bolle; ordinamento a inserimento; convoluzione diretta
tempo cubico		O(n³)	n³	Moltiplicazione ingenua di due matrici n×n. Calcolare la correlazione parziale
tempo polinomiale	P	2^O(log n) = poly(n)	n, n log n, n¹⁰	Algoritmo di Karmarkar per la programmazione lineare; algoritmo AKS
tempo quasi-polinomiale	QP	2^poly(log n)	n^log log n, n^log n	Il più noto algoritmo di approssimazione O(log² n) per il problema dell'albero di Steiner diretto
tempo subesponenziale (prima definizione)	SUBEXP	O(2^{n^ε}) per tutti gli ε > 0	O(2^{log n^{log log n}})	Assumendo le congetture della teoria della complessità, BPP è contenuta in SUBEXP^[3]
tempo subesponenziale (seconda definizione)		2^o(n)	2^{n^1/3}	Il più noto algoritmo per la scomposizione in fattori primi e per l'isomorfismo dei grafi
tempo esponenziale	E	2^O(n)	1,1ⁿ, 10ⁿ	Risolvere il problema del commesso viaggiatore usando la programmazione dinamica
tempo fattoriale		O(n!)	n!	Risolvere il problema del commesso viaggiatore attraverso il metodo forza bruta
tempo esponenziale	EXPTIME	2^poly(n)	2ⁿ, 2^n²
tempo doppio esponenziale	2-EXPTIME	2^{2^poly(n)}	2^2ⁿ	Decidere la verità di un'affermazione data nell'aritmetica di Presburger

Tempo costante

Si dice che un algoritmo è in tempo costante (scritto anche come tempo O(1)) se il valore di T(n) è vincolato da un valore che non dipende dalla dimensione dell'input. Ad esempio, accedere a qualsiasi elemento singolo in un vettore richiede tempo costante in quanto deve essere eseguita solo un'operazione per localizzarlo. Tuttavia, trovare il valore minimale in un vettore non ordinato non è un'operazione in tempo costante, in quanto è necessaria una scansione su ciascun elemento del vettore al fine di determinare il valore minimale. Quindi è un'operazione in tempo lineare, che impiega il tempo O(n). Se il numero di elementi è conosciuto in anticipo e non cambia, tuttavia, si può ancora dire che tale algoritmo si esegue in tempo costante.

Malgrado il nome "tempo costante", il tempo di esecuzione non deve essere indipendente dalla dimensione del problema, ma deve essere posto un vincolo superiore per il tempo di esecuzione indipendentemente dalla dimensione del problema. Ad esempio, il compito "scambiare i valori di a e b se necessario affinché a ≤ b" è chiamato tempo costante anche se il tempo può dipendere se sia o no già vero che a ≤ b. Tuttavia, c'è una qualche costante t tale che il tempo richiesto sia sempre al massimo t.

Ecco alcuni frammenti di codice che si eseguono in tempo costante:

int indice = 5;
int elemento = lista[indice];
if (condizione vera) then
   svolgere qualche operazione che si esegue in tempo costante
other
   svolgere qualche altra operazione che si esegue in tempo costante
per i = 1 a 100
   per j = 1 a 200
      svolgere qualche operazione che si esegue in tempo costante

Se T(n) è O(qualsiasi valore costante), questo è equivalente a ed enunciato in notazione normale come T(n) essendo O(1).

Tempo logaritmico

Si dice che un algoritmo impiega tempo logaritmico se T(n) = O(log n). A causa dell'uso del sistema numerico binario da parte dei computer, il logaritmo è frequentemente a base 2 (cioè, log₂ n, talvolta scritto lg n). Tuttavia, con il cambiamento della base per i logaritmi, log_a n e log_b n differiscono soltanto per un moltiplicatore costante, che nella notazione O grande è scartato; così O(log n) è la notazione standard per gli algoritmi in tempo logaritmico indipendentemente dalla base del logaritmo.

Gli algoritmi che impiegano tempo logaritmico si trovano comunemente nelle operazioni sugli alberi binari o quando si usa la ricerca binaria.

Un algoritmo O(log n) è considerato altamente efficiente, in quanto le operazioni da completare richieste per istanza diminuiscono con ogni istanza.

Un esempio molto semplice di questo tipo di f(n) è un algoritmo che taglia a metà una stringa. Impiegherà O(log n) (n essendo la lunghezza della stringa) dal momento che sminuzziamo la stringa a metà prima di ogni stampa (facciamo l'assunzione che console.log e str.substring si eseguano in tempo costante). Questo significa che, al fine di aumentare il numero di stampe, dobbiamo raddoppiare la lunghezza della stringa.

// Funzione per stampare ricorsivamente la metà destra di una stringa
var destra = function(str){
    var lunghezza = str.length;
    
    // Funzione di aiuto
    var aiuto = function(indice){
        
        // Caso Ricorsivo: Stampare la metà destra
        if(indice < lunghezza){
          
            // Stampa i caratteri dall'indice fino alla fine dell'array
            console.log(str.substring(indice, lunghezza));
            
            // Chiamata Ricorsiva: chiamare aiuto sulla metà destra
            aiuto(Math.ceil((lunghezza + indice)/2));
        }
        
        // Caso Base: Non fare niente
    }
    aiuto(0);
}

Tempo polilogaritmico

Si dice che un algoritmo è eseguito in tempo polilogaritmico se T(n) = O((log n)^k), per una qualche costante k. Ad esempio, l'ordinamento di una catena di matrici può essere risolto in tempo polilogaritmico su una macchina ad accesso casuale parallelo.^[4]

Tempo sublineare

Si dice che un algoritmo si esegue in tempo sublineare (spesso scritto tempo sub-lineare) se T(n) = o(n). In particolare questo include algoritmi con le complessità temporali definite sopra, nonché altri come l'algoritmo di ricerca di Grover O(n^½).

Gli algoritmi tipici che sono esatti e tuttavia si eseguono in tempo sub-lineare usano l'elaborazione parallela (come fa il calcolo del determinante della matrice NC₁), l'elaborazione non classica (come fa la ricerca di Grover), o alternativamente hanno assunzioni garantite sulla struttura degli input (come fanno la ricerca binaria in tempo logaritmico e molti algoritmi di manutenzione ad albero). Tuttavia, i linguaggi come l'insieme di tutte le stringhe che hanno 1-bit indicizzato dai primi bit log(n) possono dipendere da ogni bit dell'input ed essere però computabili in tempo sub-lineare.

Il termine specifico algoritmo in tempo sublineare è riservato solitamente ad algoritmi diversi da quelli di sopra in quanto sono eseguiti su modelli classici di macchine seriali e non sono consentite loro assunzioni anteriori sull'input.^[5] Essi possono tuttavia essere randomizzati, e in verità devono esserlo per quasi tutti i compiti più banali.

Poiché tale algoritmo deve fornire una risposta senza leggere l'intero input, i particolari dipendono fortemente dall'accesso consentito all'input. Solitamente per un input che è rappresentato come una stringa binaria b₁,...,b_k si assume che l'algoritmo possa nel tempo O(1) richiedere e ottenere il valore di b_i per qualsiasi i.

Gli algoritmi in tempo sub-lineare sono tipicamente randomizzati, e forniscono solo soluzioni approssimate. Infatti, si può facilmente dimostrare che la proprietà di una stringa binaria che ha solo zeri (e nessun uno) non è decidibile da un algoritmo in tempo sub-lineare (non approssimato). Gli algoritmi in tempo sub-lineare emergono naturalmente nelle indagini sul collaudo delle proprietà.

Tempo lineare

Si dice che un algoritmo impiega un tempo lineare, o tempo O(n), se la sua complessità temporale è O(n). Informalmente, questo significa che per dimensioni dell'input abbastanza grandi il tempo di esecuzione aumenta linearmente con la dimensione dell'input. Per esempio, una procedura che addiziona tutti gli elementi di una lista richiede un tempo proporzionale alla lunghezza della lista. Questa descrizione è lievemente inaccurata, poiché il tempo di esecuzione può deviare significativamente da una precisa proporzionalità, specialmente per piccoli valori di n.

Il tempo lineare è spesso visto come un attributo desiderabile per un algoritmo. Sono state investite molte ricerche nella creazione di algoritmi che esibiscono un tempo (quasi) lineare o migliore. Queste ricerche includono sia metodi software che hardware. Nel caso dell'hardware, alcuni algoritmi che, matematicamente parlando, non possono mai raggiungere un tempo lineare con modelli di computazione ordinari sono in grado di essere eseguiti in tempo lineare. Ci sono parecchie tecnologie hardware che sfruttano il parallelismo per ottenere questo. Un esempio è la memoria indirizzabile ai contenuti. Questo concetto di tempo lineare è usato negli algoritmi di accoppiamento delle stringhe come l'algoritmo di Boyer-Moore e l'algoritmo di Ukkonen.

Tempo linearitmico

Una funzione linearitmica (combinazione di lineare e logaritmica) è una funzione della forma n · log n (cioè un prodotto di un termine lineare e di uno logaritmico). Si dice che un algoritmo è eseguito in tempo linearitmico se T(n) = O(n log n). In confronto ad altre funzioni, una funzione linearitmica ω(n), o(n^1+ε) per ogni ε > 0, e Θ(n · log n). Perciò, un termine linearitmico cresce più velocemente di un termine lineare ma più lentamente di un qualsiasi polinomio in n con esponente strettamente maggiore di 1.

In molti casi, il tempo di esecuzione n · log n è semplicemente il risultato di eseguire un'operazione Θ(log n) n volte. Ad esempio, l'ordinamento ad albero binario crea un albero binario inserendo ciascun elemento del vettore (array) di dimensione n uno alla volta. Poiché l'operazione di inserimento su un albero binario di ricerca bilanciato impiega il tempo O(log n), l'intero algoritmo impiega un tempo linearitmico.

Gli ordinamenti comparativi richiedono nel caso peggiore almeno un numero linearitmico di comparazioni perché log(n!) = Θ(n log n), in base all'approssimazione di Stirling. Essi derivano frequentemente anche dalla relazione di ricorrenza T(n) = 2 T(n/2) + O(n).

Alcuni famosi algoritmi eseguiti in tempo linearitmico comprendono:

Quicksort ("ordinamento rapido") nel caso medio
Heap sort ("ordinamento a catasta"), merge sort ("ordinamento per fusione"), introsort ("ordinamento introspettivo"), binary tree sort ("ordinamento ad albero binario"), smoothsort ("ordinamento liscio"), patience sorting ("solitario"), ecc. nel caso peggiore
Trasformate di Fourier veloci
Calcolo della matrice di Monge

Tempo quasi-lineare

Una generalizzazione del tempo linearitmico è il tempo quasi-lineare. Si dice che un algoritmo funziona in tempo quasi-lineare se T(n) = O(n log^k n) per una qualsiasi costante k; il tempo linearitmico è il caso k = 1. Gli algoritmi in tempo quasi-lineare sono anche o(n^1+ε) per ogni ε > 0, e funzionano più velocemente di un qualsiasi polinomio in n con esponente strettamente maggiore di 1.

Gli algoritmi che si eseguono in tempo in quasi-lineare, in aggiunta agli algoritmi linearitmici elencati sopra, includono:

In-place merge sort ("ordinamento per fusione in loco"), O(n log² n)

Tempo subquadratico

Si dice che un algoritmo è in tempo subquadratico se T(n) = o(n²).

Per esempio, la maggior parte degli algoritmi di ordinamento ingenuo basati sui confronti sono quadratici (ad es. l'ordinamento a inserimento), ma si possono trovare algoritmi più avanzati che sono subquadratici (ad es. l'ordinamento di Shell). Nessun ordinamento multiuso è eseguito in tempo lineare, ma il cambiamento da quadratico a subquadratico è di grande importanza fiscale.

Tempo polinomiale

Si dice che un algoritmo è in tempo polinomiale se il suo tempo di esecuzione è limitato superiormente da un'espressione polinomiale nella dimensione dell'input per l'algoritmo, cioè, T(n) = O(n^k) per una qualche costante k.^[1]^[6] I problemi per i quali esiste un algoritmo deterministico in tempo polinomiale appartengono alla classe di complessità P, che è centrale nel campo della teoria della complessità computazionale. La tesi di Cobham afferma che il tempo polinomiale è un sinonimo per "trattabile", "fattibile", "efficiente" o "veloce".^[7]

Alcuni esempi di algoritmi in tempo polinomiale:

L'algoritmo di ordinamento quicksort su n interi svolge al massimo $An^{2}$ operazioni per qualche costante A. Perciò si esegue nel tempo polinomiale $O(n^{2})$ ed è un algoritmo in tempo polinomiale.
Tutte le operazioni aritmetiche basilari (addizione, sottrazione, moltiplicazione, divisione e confronto) possono essere fatte in tempo polinomiale.
Gli accoppiamenti massimi nei grafi si possono trovare in tempo polinomiale.

Tempo fortemente e debolmente polinomiale

In alcuni contesti, specialmente nell'ottimizzazione, si differenzia tra algoritmi in tempo fortemente polinomiale e in tempo debolmente polinomiale. Questi due concetti sono rilevanti soltanto se gli input per gli algoritmi consistono di interi.

Il tempo fortemente polinomiale è definito nel modello aritmetico di computazione. In questo modello di computazione le operazioni aritmetiche basilari (addizione, sottrazione, moltiplicazione, divisione e confronto) impiegano un passo in tempo unitario per essere svolte, indipendentemente dalle dimensioni degli operandi. L'algoritmo si esegue in tempo fortemente polinomiale se^[8]

il numero di operazioni nel modello aritmetico di computazione è limitato da un polinomio nel numero di interi dell'istanza dell'input; e
lo spazio usato dall'algoritmo è limitato da un polinomio nella dimensione dell'input.

Qualsiasi algoritmo con queste due proprietà può essere convertito in un algoritmo di tempo polinomiale sostituendo le operazioni aritmetiche mediante algoritmi idonei a svolgere le operazioni aritmetiche su una macchina di Turing. Se il secondo dei suddetti requisiti non è soddisfatto, allora questo non è più vero. Dato l'intero $2^{n}$ (che occupa uno spazio proporzionale a n), è possibile computare $2^{2^{n}}$ con n moltiplicazioni usando la quadratura ripetuta. Tuttavia, lo spazio usato per rappresentare $2^{2^{n}}$ è proporzionale a $2^{n}$ , e perciò esponenziale piuttosto che polinomiale nello spazio usato per rappresentare l'input. Quindi, non è possibile eseguire questa computazione in tempo polinomiale in una macchina di Turing, ma è possibile computarla polinomialmente mediante molte operazioni aritmetiche.

Per converso, ci sono algoritmi che si eseguono in un numero di passi della macchina di Turing limitato da un polinomio per quanto riguarda la lunghezza dell'input in codice binario, ma non impiegano un numero di operazioni aritmetiche limitato da un polinomio per quanto riguarda il numero dei numeri dell'input. L'algoritmo euclideo per calcolare il massimo comun divisore di due interi è un esempio. Dati due interi $a$ e $b$ il tempo di esecuzione dell'algoritmo è limitato da $O((\log \ a+\log \ b)^{2})$ passi della macchina di Turing. Questo è polinomiale nella dimensione di una rappresentazione binaria di $a$ e $b$ in quanto la dimensione di tale rappresentazione è grosso modo $\log \ a+\log \ b$ . Allo stesso tempo, il numero di operazioni aritmetiche non può essere limitato dal numero di interi nell'input (che è costante in questo caso: ci sono sempre soltanto due interi nell'input). A causa di quest'ultima osservazione, l'algoritmo non funziona in tempo strettamente polinomiale. Il suo tempo di esecuzione reale dipende dalle ampiezze di $a$ e $b$ e non soltanto dal numero di interi nell'input.

Un algoritmo che si esegue in tempo polinomiale ma che non è fortemente polinomiale si dice che si esegue in tempo debolmente polinomiale.^[9] Un esempio ben noto di un problema per il quale si conosce un algoritmo in tempo debolmente polinomiale, ma non si conosce se ammetta un algoritmo in tempo fortemente polinomiale, è la programmazione lineare. Il tempo debolmente polinomiale non dovrebbe essere confuso con il tempo pseudopolinomiale.

Classi di complessità

Il concetto di tempo polinomiale conduce a varie classi di complessità nella teoria della complessità computazionale. Alcune classi importanti definite usando il tempo polinomiale sono le seguenti.

P: La classe di complessità dei problemi decisionali che possono essere risolti su una macchina di Turing deterministica in tempo polinomiale.
NP: La classe di complessità dei problemi decisionali che possono essere risolti su una macchina di Turing non deterministica in tempo polinomiale.
ZPP: La classe di complessità dei problemi decisionali che possono essere risolti con errore zero su una macchina di Turing probabilistica in tempo polinomiale.
RP: La classe di complessità dei problemi decisionali che possono essere risolti con errore da 1 lato su una macchina di Turing probabilistica in tempo polinomiale.
BPP: La classe di complessità dei problemi decisionali che possono essere risolti con errore da 2 lati su una macchina di Turing probabilistica in tempo polinomiale.
BQP: La classe di complessità dei problemi decisionali che possono essere risolti con errore da 2 lati su una macchina di Turing quantistica in tempo polinomiale.

P è la più piccola classe di complessità temporale su una macchina deterministica che sia robusta in termini di cambiamenti dei modelli di macchina. (Ad esempio, un cambiamento da una macchina di Turing a nastro singolo a una macchina multinastro può condurre a un aumento di velocità quadratico, ma qualsiasi algoritmo che funziona in tempo polinomiale in base a un modello lo fa anche sull'altro.) Qualsiasi data macchina astratta avrà una classe di complessità corrispondente ai problemi che possono essere risolti in tempo polinomiale su quella macchina.

Tempo superpolinomiale

Si dice che un algoritmo impiega un tempo superpolinomiale se T(n) non è limitato superiormente da nessun polinomio. È il tempo ω(n^c) per tutte le costanti c, dove n è il parametro dell'entrata, tipicamente il numero di bit nell'input.

Ad esempio, un algoritmo che viene eseguito per 2ⁿ passi su un input di dimensione n richiede un tempo superpolinomiale (più specificamente, un tempo esponenziale).

Un algoritmo che usa risorse esponenziali è chiaramente superpolinomiale, ma alcuni algoritmi sono solo molto debolmente superpolinomiali. Ad esempio, il test di primalità di Adleman-Pomerance-Rumely si esegue per un tempo n^{O(log log n)} su entrate di n bit; questo cresce più velocemente di qualsiasi polinomio per n abbastanza grande, ma la dimensione dell'input deve diventare grande in modo poco realistico prima che un polinomio di piccolo grado non riesca più a dominarlo.

Un algoritmo che richiede un tempo superpolinomiale giace al di fuori della classe di complessità P. La tesi di Cobham postula che questi algoritmi siano poco pratici, e in molti casi lo sono. Poiché il problema di P contro NP è irrisolto, attualmente non si conosce nessun algoritmo per un problema NP-completo che funzioni in tempo polinomiale.

Tempo quasi-polinomiale

Gli algoritmi in tempo quasi-polinomiale sono algoritmi che si eseguono più lentamente del tempo polinomiale, tuttavia non così lentamente da essere in tempo esponenziale. Il tempo di esecuzione del caso peggiore di un algoritmo in tempo quasi-polinomiale è $2^{O((\log n)^{c})}$ per una qualche c fissa. L'algoritmo classico più conosciuto per la fattorizzazione degli interi, il crivello dei campi di numeri generale, che si esegue nel tempo di circa $2^{{\tilde {O}}(n^{1/3})}$ non è quasi-polinomiale, dal momento che il tempo di esecuzione non può essere espresso come $2^{O((\log n)^{c})}$ per una qualche c fissa. Se la costante c nella definizione degli algoritmi in tempo quasi-polinomiale è uguale a 1, otteniamo un algoritmo in tempo polinomiale, e se è minore di 1, otteniamo un algoritmo in tempo sub-lineare.

Gli algoritmi in tempo quasi-polinomiale tipicamente nascono nelle riduzioni da un problema NP-difficile a un altro problema. Ad esempio, si può prendere l'istanza di un problema NP difficile, diciamo 3SAT, e convertirlo in un'istanza di un altro problema B, ma la dimensione dell'istanza diventa $2^{O((\log n)^{c})}$ . In quel caso, questa riduzione non prova che il problema B è NP-difficile; questa riduzione mostra soltanto che non c'è alcun algoritmo polinomiale per B a meno che non ci sia un algoritmo quasi-polinomiale per 3SAT (e così per tutti quelli di NP). Similmente, ci sono alcuni problemi per i quali conosciamo algoritmi in tempo quasi polinomiale, ma non si conosce un algoritmo in tempo polinomiale. Tali problemi sorgono negli algoritmi di approssimazione; un esempio famoso è il problema dell'albero di Steiner, per il quale c'è un algoritmo di approssimazione in tempo quasi polinomiale che raggiunge un fattore di approssimazione di $O(\log ^{3}n)$ (n essendo il numero dei vertici), ma dimostrare l'esistenza di tale algoritmo in tempo polinomiale è un problema aperto

La classe di complessità QP consiste di tutti i problemi che hanno algoritmi in tempo quasi-polinomiale. Può essere definita in termini di DTIME nel modo seguente.^[10]

{\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{(\log n)^{c}})

Relazione con i problemi NP-completi

Nella teoria della complessità, il problema irrisolto P contro NP chiede se tutti i problemi in NP hanno algoritmi in tempo polinomiale. Tutti gli algoritmi più noti per problemi NP-completi come 3SAT e altri, impiegano un tempo esponenziale. In effetti, si congettura per molti problemi naturali NP-completi che non abbiamo algoritmi in tempo subesponenziale. Qui si assume che "tempo subesponenziale" significhi la seconda definizione presentata sopra. (D'altro canto, molti problemi dei grafi rappresentati nel modo naturale mediante matrici di adiacenze sono risolvibili in tempo subesponenziale semplicemente perché la dimensione dell'input è il quadrato del numero dei vertici.) Questa congettura (per il problema k-SAT) è nota come l'ipotesi del tempo esponenziale.^[11] Poiché si congettura che i problemi NP-completi non abbiano algoritmi in tempo quasi-polinomiale, alcuni risultati di inapprossimabilità nel campo degli algoritmi di approssimazione fanno l'assunzione che i problemi NP-completi non abbiano algoritmi in tempo quasi-polinomiale. Ad esempio, vedi i risultati di inapprossimabilità conosciuti per il problema di copertura degli insiemi.

Tempo subesponenziale

Il termine tempo subesponenziale si usa per esprimere che il tempo di esecuzione di un qualche algoritmo può crescere più velocemente di qualsiasi polinomio, ma è ancora significativamente più piccolo di un'esponenziale. In questo senso, i problemi che hanno algoritmi in tempo subesponenziale sono alquanto più trattabili di quelli che hanno soltanto algoritmi esponenziali. Sulla definizione precisa di "subesponenziale" generalmente non vi è accordo,^[12] e noi elenchiamo le due più ampiamente usate sotto.

Prima definizione

Si dice che un problema è risolvibile in tempo subesponenziale se può essere risolto in tempi di esecuzione i cui logaritmi aumentano meno di qualsiasi polinomio dato. Più precisamente, un problema è in tempo subesponenziale se per ogni ε > 0 esiste un algoritmo che risolve il problema nel tempo O(2^{n^ε}). L'insieme di tutti i problemi di questo tipo è la classe di complessità SUBEXP che può essere definita in termin di DTIME nel modo seguente.^[3]^[13]^[14]

{\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)

Si noti che questa nozione di subesponenziale è non uniforme in termini di ε, nel senso che ε non fa parte dell'input e ciascun ε può avere il proprio algoritmo per il problema.

Seconda definizione

Alcuni autori definiscono il tempo subesponenziale come tempi di esecuzione in 2^O(n).^[11]^[15]^[16] Questa definizione consente tempi di esecuzione maggiori della prima definizione di tempo subesponenziale. Un esempio di un tale algoritmo in tempo subesponenziale è l'algoritmo classico più noto per la fattorizzazione degli interi, il crivello dei campi di numeri generale, che funziona nel tempo di circa $2^{{\tilde {O}}(n^{1/3})}$ , dove la lunghezza dell'input è n. Un altro esempio è l'algoritmo più noto per il problema dell'isomorfismo dei grafi, che funziona nel tempo 2^{O(√(n log n))}.

Si noti che fa differenza se all'algoritmo si permette di essere subesponenziale nella dimensione dell'istanza, del numero dei vertici o del numero degli spigoli. Nella complessità parametrizzata, questa differenza è resa esplicita considerando le coppie $(L,k)$ di problemi decisionali e parametri k. SUBEPT è la classe di tutti i problemi parametrizzati che si eseguono in tempo subesponenziale in k e polinomiale nella dimensione n:^[17]

{\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right).

Più precisamente, SUBEPT è la classe di tutti i problemi parametrizzati $(L,k)$ per i quali vi è una funzione computabile $f:\mathbb {N} \to \mathbb {N}$ con $f\in o(k)$ e un algoritmo che decide L nel tempo $2^{f(k)}\cdot {\text{poly}}(n)$ .

Ipotesi del tempo esponenziale

L'ipotesi del tempo esponenziale o ITE (in inglese exponential time hypothesis, ETH) è che 3SAT, il problema di soddisfacibilità delle formule booleane in forma normale congiuntiva con al massimo tre letterali per clausola e con n variabili, non possa essere risolto nel tempo 2^O(n). Più precisamente, l'ipotesi è che ci sia una qualche costante assoluta c > 0 tale che 3SAT non possa essere deciso nel tempo 2^cn da nessuna macchina di Turing deterministica. Con m che denota il numero di clausole, ITE è equivalente all'ipotesi che kSAT non possa essere risolto nel tempo 2^O(m) per qualsiasi intero k ≥ 3.^[18] L'ipotesi del tempo esponenziale implica P ≠ NP.

Tempo esponenziale

Si dice che un algoritmo è in tempo esponenziale, se T(n) è limitato superiormente da 2^poly(n), dove poly(n) è un qualche polinomio in n. Più formalmente, un algoritmo è in tempo esponenziale se T(n) è limitato da O(2^{n^k}) per una qualche costante k. I problemi che ammettono algoritmi in tempo esponenziale su una macchina di Turing deterministica formano la classe di complessità conosciuta come EXP.

{\text{EXP}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{n^{c}}\right)

Talvolta, il tempo esponenziale si usa per riferirsi ad algoritmi che hanno T(n) = 2^O(n), dove l'esponente è al massimo una funzione lineare di n. Questo dà origine alla classe di complessità E.

{\text{E}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{cn}\right)

Tempo doppio esponenziale

Si dice che un algoritmo è in tempo doppio esponenziale se T(n) è limitato superiormente da 2^{2^poly(n)}, dove poly(n) è un qualche polinomio in n. Tali algoritmi appartengono alla classe di complessità 2-EXPTIME.

{\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{2^{n^{c}}})

Algoritmi ben noti in tempo doppio esponenziale includono:

Le procedure decisionali per l'aritmetica di Presburger
Computare una base di Gröbner (nel caso peggiore)
L'eliminazione dei quantificatori sui campi reali chiusi impiega almeno un tempo doppio esponenziale (ma non si conosce nemmeno come computabile in ELEMENTARY).

Note

^ ^a ^b Michael Sipser, Introduction to the Theory of Computation, Course Technology Inc, 2006, ISBN 0-619-21764-2.
^ Kurt Mehlhorn e Stefan Naher, Bounded ordered dictionaries in O(log log N) time and O(n) space, in Information Processing Letters, vol. 35, n. 4, 1990, p. 183, DOI:10.1016/0020-0190(90)90022-P.
^ ^a ^b László Babai, Lance Fortnow, N. Nisan e Avi Wigderson, BPP has subexponential time simulations unless EXPTIME has publishable proofs, in Computational Complexity, vol. 3, n. 4, Berlino, New York, Springer-Verlag, 1993, pp. 307–318, DOI:10.1007/BF01275486.
^ Phillip G. Bradford, Gregory J. E. Rawlins e Gregory E. Shannon, Efficient Matrix Chain Ordering in Polylog Time, in SIAM Journal on Computing, vol. 27, n. 2, Filadelfia, Society for Industrial and Applied Mathematics, 1998, pp. 466–490, DOI:10.1137/S0097539794270698, ISSN 1095-7111 (WC · ACNP).
^ Ravi Kumar e Ronitt Rubinfeld, Sublinear time algorithms (PDF), in SIGACT News, vol. 34, n. 4, 2003, pp. 57–67.
^ Christos H. Papadimitriou, Computational complexity, Reading, Mass., Addison-Wesley, 1994, ISBN 0-201-53082-1.
^ Alan Cobham, The intrinsic computational difficulty of functions, in Proc. Logic, Methodology, and Philosophy of Science II, North Holland, 1965.
^ Martin Grötschel, László Lovász, Alexander Schrijver, Complexity, Oracles, and Numerical Computation, in Geometric Algorithms and Combinatorial Optimization, Springer, 1988, ISBN 0-387-13624-X.
^ Alexander Schrijver, Preliminaries on algorithms and Complexity, in Combinatorial Optimization: Polyhedra and Efficiency, vol. 1, Springer, 2003, ISBN 3-540-44389-4.
^ ComplexityZoo: "Class QP: Quasipolynomial-Time" Archiviato il 22 dicembre 2015 in Internet Archive.
^ ^a ^b R. Impagliazzo e R. Paturi, On the complexity of k-SAT, in Journal of Computer and System Sciences, vol. 62, n. 2, Elsevier, 2001, pp. 367–375, DOI:10.1006/jcss.2000.1727, ISSN 1090-2724 (WC · ACNP).
^ Aaronson, Scott, A not-quite-exponential dilemma, in Shtetl-Optimized, 5 aprile 2009. URL consultato il 2 dicembre 2009.
^ P. Moser, Baire's Categories on Small Complexity Classes, in Lecture Notes in Computer Science, Berlino, New York, Springer-Verlag, 2003, pp. 333–342, ISSN 0302-9743 (WC · ACNP).
^ P.B. Miltersen, DERANDOMIZING COMPLEXITY CLASSES, in Handbook of Randomized Computing, Kluwer Academic Pub, 2001, p. 843.
^ Greg Kuperberg, A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem, in SIAM Journal on Computing, vol. 35, n. 1, Filadelfia, Society for Industrial and Applied Mathematics, 2005, p. 188, ISSN 1095-7111 (WC · ACNP).
^ Oded Regev, A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space, quant-ph, 2004, arXiv:quant-ph/0406151v1.
^ Jörg Flum e Martin Grohe, Parameterized Complexity Theory, Springer, 2006, p. 417, ISBN 978-3-540-29952-3. URL consultato il 5 marzo 2010 (archiviato dall'url originale il 18 novembre 2007).
^ R. Impagliazzo, R. Paturi e F. Zane, Which problems have strongly exponential complexity?, in Journal of Computer and System Sciences, vol. 63, n. 4, 2001, pp. 512–530, DOI:10.1006/jcss.2001.1774.

Voci correlate

Notazione L

Collegamenti esterni

(EN) Denis Howe, time complexity, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL

Portale Informatica

Portale Matematica

[Sipser-1] Michael Sipser, Introduction to the Theory of Computation, Course Technology Inc, 2006, ISBN 0-619-21764-2.

[2] Kurt Mehlhorn e Stefan Naher, Bounded ordered dictionaries in O(log log N) time and O(n) space, in Information Processing Letters, vol. 35, n. 4, 1990, p. 183, DOI:10.1016/0020-0190(90)90022-P.

[bpp-3] László Babai, Lance Fortnow, N. Nisan e Avi Wigderson, BPP has subexponential time simulations unless EXPTIME has publishable proofs, in Computational Complexity, vol. 3, n. 4, Berlino, New York, Springer-Verlag, 1993, pp. 307–318, DOI:10.1007/BF01275486.

[4] Phillip G. Bradford, Gregory J. E. Rawlins e Gregory E. Shannon, Efficient Matrix Chain Ordering in Polylog Time, in SIAM Journal on Computing, vol. 27, n. 2, Filadelfia, Society for Industrial and Applied Mathematics, 1998, pp. 466–490, DOI:10.1137/S0097539794270698, ISSN 1095-7111 (WC · ACNP).

[5] Ravi Kumar e Ronitt Rubinfeld, Sublinear time algorithms (PDF), in SIGACT News, vol. 34, n. 4, 2003, pp. 57–67.

[6] Christos H. Papadimitriou, Computational complexity, Reading, Mass., Addison-Wesley, 1994, ISBN 0-201-53082-1.

[7] Alan Cobham, The intrinsic computational difficulty of functions, in Proc. Logic, Methodology, and Philosophy of Science II, North Holland, 1965.

[8] Martin Grötschel, László Lovász, Alexander Schrijver, Complexity, Oracles, and Numerical Computation, in Geometric Algorithms and Combinatorial Optimization, Springer, 1988, ISBN 0-387-13624-X.

[9] Alexander Schrijver, Preliminaries on algorithms and Complexity, in Combinatorial Optimization: Polyhedra and Efficiency, vol. 1, Springer, 2003, ISBN 3-540-44389-4.

[10] ComplexityZoo: "Class QP: Quasipolynomial-Time" Archiviato il 22 dicembre 2015 in Internet Archive.

[ETH-11] R. Impagliazzo e R. Paturi, On the complexity of k-SAT, in Journal of Computer and System Sciences, vol. 62, n. 2, Elsevier, 2001, pp. 367–375, DOI:10.1006/jcss.2000.1727, ISSN 1090-2724 (WC · ACNP).

[12] Aaronson, Scott, A not-quite-exponential dilemma, in Shtetl-Optimized, 5 aprile 2009. URL consultato il 2 dicembre 2009.

[13] P. Moser, Baire's Categories on Small Complexity Classes, in Lecture Notes in Computer Science, Berlino, New York, Springer-Verlag, 2003, pp. 333–342, ISSN 0302-9743 (WC · ACNP).

[14] P.B. Miltersen, DERANDOMIZING COMPLEXITY CLASSES, in Handbook of Randomized Computing, Kluwer Academic Pub, 2001, p. 843.

[15] Greg Kuperberg, A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem, in SIAM Journal on Computing, vol. 35, n. 1, Filadelfia, Society for Industrial and Applied Mathematics, 2005, p. 188, ISSN 1095-7111 (WC · ACNP).

[16] Oded Regev, A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space, quant-ph, 2004, arXiv:quant-ph/0406151v1.

[17] Jörg Flum e Martin Grohe, Parameterized Complexity Theory, Springer, 2006, p. 417, ISBN 978-3-540-29952-3. URL consultato il 5 marzo 2010 (archiviato dall'url originale il 18 novembre 2007).

[18] R. Impagliazzo, R. Paturi e F. Zane, Which problems have strongly exponential complexity?, in Journal of Computer and System Sciences, vol. 63, n. 4, 2001, pp. 512–530, DOI:10.1006/jcss.2001.1774.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]