Complexitatea timpului

În informatică , complexitatea timpului unui algoritm cuantifică timpul necesar unui algoritm pentru a fi executat în funcție de lungimea șirului care reprezintă intrarea ^[1] ^{: 226} . Complexitatea timpului unui algoritm este exprimată în mod obișnuit folosind notația O mare , care exclude coeficienții și termenii de ordin inferior. Când este exprimat în acest fel, se spune că complexitatea timpului este descrisă asimptotic , adică atunci când dimensiunea intrărilor merge la infinit. De exemplu, dacă timpul necesar unui algoritm pentru toate intrările dimensiunii n este cel mult 5 n ³ + 3 n , complexitatea timpului asimptotic este O ( n ³ ).

Complexitatea timpului este de obicei estimată prin numărarea numărului de operații elementare efectuate de algoritm, unde o operație elementară necesită o perioadă fixă de timp pentru a efectua. Astfel, timpul necesar și numărul de operații elementare efectuate de algoritm diferă cel mult de un factor constant.

Deoarece timpul de execuție al unui algoritm poate varia cu intrări diferite de aceeași dimensiune, folosim în mod obișnuit complexitatea timpului cel mai rău a unui algoritm, notat ca T ( n ) , care este definit ca cantitatea maximă de timp petrecut pe o singură intrare de mărime n . Complexitățile de timp sunt clasificate în funcție de natura funcției T ( n ). De exemplu, un algoritm cu T ( n ) = O ( n ) se numește algoritm de timp liniar, iar un algoritm cu T ( n ) = O (2 ⁿ ) se spune că este un algoritm de timp exponențial.

Tabel comun de complexitate a timpului

Același subiect în detaliu: Complexitatea Computațională .

Tabelul următor rezumă câteva clase de complexitate temporală întâlnite în mod obișnuit. În tabel, poli ( x ) = x ^{O (1)} , adică polinom în x .

Nume	Clasa de complexitate	Timp de execuție ( T ( n ))	Exemple de timpi de execuție	Exemple de algoritmi
timp constant		O (1)	10	Determinați dacă un număr întreg (reprezentat în binar) este par sau impar
Ackermann timp invers		O ( α ( n ))		Timp amortizat pentru o operație care utilizează un set disjunct
timpul logaritmic iterat		O ( log * n )		Colorarea distribuită a ciclurilor
log-logaritmic		O (jurnal jurnal n )	Timp amortizat pentru o operație care utilizează o coadă de prioritate constrânsă ^[2]
timpul logaritmic	DLOGTIME	O (jurnal n )	jurnal n , jurnal ( n ² )	căutare binară
timpul polilogaritmic		poli (jurnal n )	(jurnal n ) ²
puterea fracționată		O ( n ^c ) unde 0 <c <1	n ^1/2 , n ^2/3	Căutați într-un copac kd
timpul liniar		O ( n )	n	Găsiți cel mai mic element dintr-un vector neordonat
timp "n asterisc jurnal n"		O ( n log * n )		Algoritm de triangulare a poligonului Seidel
timpul liniaritmic		O ( n jurnal n )	n jurnal n , jurnal n !	Cel mai rapid tip comparativ
timpul pătratic		O ( n ² )	n ²	Sortarea cu bule ; sortare prin inserție ; convoluție directă
timpul cubic		O ( n ³ )	n ³	Multiplicare Naiv a două n × n matrici. Calculați corelația parțială
timpul polinomial	P.	2 ^{O (log n )} = poli ( n )	n , n log n , n ¹⁰	Algoritmul lui Karmarkar pentru programarea liniară ; Algoritmul AKS
timpul cvasi-polinomial	QP	2 ^{poli (jurnal n )}	n ^{jurnal jurnal n} , n ^{jurnal n}	Cel mai cunoscut algoritm de aproximare O (log ² n ) pentru problema directă a arborelui Steiner
timpul subexponențial (prima definiție)	SUBEXP	O (2 ^{n ^ε} ) pentru toate ε > 0	O ^(log 2 ^{n ^{log log n)}}	Presupunând presupunerile teoriei complexității, BPP este conținut în SUBEXP ^[3]
timpul subexponențial (a doua definiție)		2 ^{o ( n )}	2 ^{n ^1/3}	Cel mai cunoscut algoritm pentru factorizarea primă și izomorfismul graficelor
timpul exponențial	ȘI	2 ^{O ( n )}	1,1 ⁿ , 10 ⁿ	Rezolvați problema vânzătorului călător folosind programarea dinamică
timpul factorial		O ( n !)	n !	Rezolvarea problemei vânzătorului călător prin metoda forței brute
timpul exponențial	EXPTIM	2 ^{poli ( n )}	2 ⁿ , 2 ^{n ²}
timp exponențial dublu	2-EXPTIME	2 ^{2 ^{poli ( n )}}	2 ^{2 ^nr}	Decideți adevărul unei afirmații date în aritmetica Presburger

Timp constant

Se spune că un algoritm este în timp constant (scris și ca O (1) timp ) dacă valoarea lui T ( n ) este constrânsă de o valoare care nu depinde de dimensiunea intrării. De exemplu, accesarea oricărui element dintr-un vector necesită timp constant, deoarece trebuie efectuată o singură operație pentru localizarea acestuia. Cu toate acestea, găsirea valorii minime într-un vector neordonat nu este o operație de timp constantă, deoarece este necesară o scanare pe fiecare element al vectorului pentru a determina valoarea minimă. Deci este o operație de timp liniară, care durează O ( n ) timp. Dacă numărul elementelor este cunoscut din timp și nu se modifică, se poate spune totuși că acest algoritm rulează în timp constant.

În ciuda denumirii „timp constant”, timpul de execuție nu trebuie să fie independent de dimensiunea problemei, dar trebuie să se pună o constrângere mai mare asupra timpului de execuție, indiferent de dimensiunea problemei. De exemplu, sarcina „schimbă valorile lui a și b, dacă este necesar, astfel încât a ≤ b ” să fie numit timp constant, chiar dacă timpul poate depinde dacă este deja adevărat că a ≤ b . Cu toate acestea, există unele constante t astfel încât timpul necesar este întotdeauna cel mult t .

Iată câteva fragmente de cod care rulează în timp constant:

 int index = 5;
int element = listă [index];
if (condiție adevărată) atunci
   efectuați o operație care se efectuează în timp constant
alte
   efectuați o altă operație care se efectuează în timp constant
pentru i = 1 până la 100
   pentru j = 1 până la 200
      efectuați o operație care se efectuează în timp constant

Dacă T ( n ) este O ( orice valoare constantă ), aceasta este echivalentă și menționată în notație normală ca T ( n ) fiind O (1).

Timpul logaritmic

Același subiect în detaliu: creșterea logaritmică .

Se spune că un algoritm ia timp logaritmic dacă T ( n ) = O (log n ) . Datorită utilizării sistemului de numere binare de către computere, logaritmul este frecvent baza 2 (adică log ₂ n , uneori scris lg n ). Cu toate acestea, pe măsură ce se modifică baza logaritmilor, log _a n și log _b n diferă doar printr-un multiplicator constant, care în notația O mare este aruncat; deci O (log n ) este notația standard pentru algoritmi de timp logaritmici, indiferent de baza logaritmului.

Algoritmii care necesită timp logaritmic se găsesc în mod obișnuit în operațiile de arbore binar sau când se utilizează căutarea binară .

Un algoritm O (log n ) este considerat extrem de eficient, deoarece operațiunile necesare pentru a finaliza pe instanță scad cu fiecare instanță.

Un exemplu foarte simplu al acestui tip de f ( n ) este un algoritm care taie un șir în două. Va lua O (log n ) ( n fiind lungimea șirului), deoarece am tăiat șirul în jumătate înainte de fiecare tipărire (să presupunem că console.log și str.substring rulează în timp constant). Aceasta înseamnă că, pentru a crește numărul de tipăriri, trebuie să dublăm lungimea șirului.

 // Funcție pentru a imprima recursiv jumătatea dreaptă a unui șir
var dreapta = funcție ( str ) {
    var lungime = str . lungime ;
    
    // Funcția de ajutor
    var ajutor = funcție ( index ) {
        
        // Caz recursiv: tipăriți jumătatea dreaptă
        if ( index < lungime ) {
          
            // Imprimați caracterele din index până la sfârșitul matricei
            consolă . log ( str . sub șir ( index , lungime ));
            
            // Apel recursiv: solicitați ajutor în jumătatea dreaptă
            ajutor ( Mat . plafon (( lungime + index ) / 2 ));
        }
        
        // Caz de bază: nu faceți nimic
    }
    ajutor ( 0 );
}

Timp polilogaritmic

Se spune că un algoritm este executat în timp polilogaritmic dacă T ( n ) = O ((log n ) ^k ), pentru o constantă k . De exemplu, ordonarea unui lanț de matrice poate fi rezolvată în timp polilogaritmic pe o mașină cu acces aleatoriu paralel . ^[4]

Timpul subliniar

Se spune că un algoritm rulează în timp subliniar (adesea scris ca timp subliniar ) dacă T ( n ) = o ( n ). În special, aceasta include algoritmi cu complexitatea temporală definită mai sus, precum și alții, cum ar fi algoritmul de căutare Grover O ( n ^½ ).

Algoritmii tipici care sunt exacți și totuși rulează în timp sub-liniar utilizează procesarea paralelă (la fel ca și calculul determinantului matricei NC ₁ ), procesarea neclasică (la fel ca și cercetarea lui Grover) sau, alternativ, au ipoteze garantate asupra intrării structură (la fel ca și căutarea binară logaritmică și mulți algoritmi de întreținere a arborelui). Cu toate acestea, limbaje precum setul tuturor șirurilor care au 1-bit indexat de primii biți log (n) pot depinde de fiecare bit al intrării și totuși pot fi calculate în timp sub-liniar.

Termenul specific algoritm de timp subliniar este de obicei rezervat pentru alți algoritmi decât cei de mai sus, deoarece sunt realizați pe modele clasice de mașini seriale și ipotezele lor anterioare privind intrarea nu sunt permise. ^[5] Cu toate acestea, ele pot fi randomizate și, într-adevăr, trebuie să fie pentru aproape toate sarcinile mai banale.

Deoarece acest algoritm trebuie să ofere un răspuns fără a citi întreaga intrare, detaliile depind puternic de accesul permis la intrare. De obicei pentru o intrare care este reprezentată ca un șir binar b ₁ , ..., b _k se presupune că algoritmul poate solicita și obține în timp O (1) valoarea lui b _i pentru orice i .

Algoritmii de timp sub-liniari sunt de obicei randomizați, oferind doar soluții aproximative . De fapt, se poate arăta cu ușurință că proprietatea unui șir binar care are doar zerouri (și nu există) nu poate fi decisă de un algoritm de timp sub-liniar (ne-aproximativ). Algoritmii timpului subliniar apar în mod natural în investigațiile de testare a proprietăților .

Timpul liniar

Se spune că un algoritm folosește timp liniar sau timp O ( n ) , dacă complexitatea sa de timp este O ( n ). În mod informal, aceasta înseamnă că pentru dimensiuni de intrare suficient de mari, timpul de rulare crește liniar cu dimensiunea de intrare. De exemplu, o procedură care adaugă toate elementele unei liste necesită timp proporțional cu lungimea listei. Această descriere este ușor inexactă, deoarece timpul de rulare se poate abate semnificativ de la o proporționalitate precisă, în special pentru valori mici de n .

Timpul liniar este adesea văzut ca un atribut de dorit pentru un algoritm. S-au investit multe cercetări în crearea algoritmilor care prezintă timp (aproape) liniar sau mai bun. Aceste căutări includ atât metode software, cât și hardware. În cazul hardware-ului, unii algoritmi care, matematic vorbind, nu pot ajunge niciodată la timp liniar cu modelele obișnuite de calcul pot fi executați în timp liniar. Există mai multe tehnologii hardware care profită de paralelism pentru a realiza acest lucru. Un exemplu este memoria adresabilă prin conținut . Acest concept de timp liniar este utilizat în algoritmi de cuplare de șiruri, cum ar fi algoritmul Boyer-Moore și algoritmul Ukkonen .

Timpul liniaritmic

O funcție liniaritmică ( combinație de liniar și logaritmic ) este o funcție de forma n · log n (adică un produs al unui termen liniar și logaritmic ). Se spune că un algoritm este executat în timp liniar dacă T ( n ) = O ( n log n ) . În comparație cu alte funcții, o funcție linearitmică ω ( n ), o ( n ^{1 + ε} ) pentru fiecare ε> 0 și Θ ( n · log n ). Prin urmare, un termen linearitmic crește mai repede decât un termen liniar, dar mai lent decât orice polinom din n cu un exponent strict mai mare de 1.

În multe cazuri, timpul de funcționare n · log n este pur și simplu rezultatul efectuării unei operații Θ (log n ) n ori. De exemplu, sortarea binară a arborelui creează un arbore binar prin inserarea fiecărui element al matricei de dimensiuni n unul câte unul. Deoarece operația de inserare pe un arbore de căutare binar echilibrat necesită timp O (log n ), întregul algoritm necesită timp liniaritmic.

Ordonările comparative necesită în cel mai rău caz cel puțin un număr liniaritmic de comparații, deoarece log ( n !) = Θ ( n log n ), pe baza aproximării Stirling . De asemenea, derivă frecvent din relația de recurență T ( n ) = 2 T ( n / 2) + O ( n ).

Unii algoritmi populari efectuați în time-lapse liniar includ:

Quicksort („sortare rapidă”) în carcasa din mijloc
Heap sortare , îmbinare sortare , introsort , arbore binar de sortare, smoothsort , răbdare de sortare ( "singur"), etc. în cel mai rău caz
Transformate Fourier rapide
Calculul matricei Monge

Timp aproape liniar

O generalizare a timpului liniaritmic este timpul cvasiliniar . Se spune că un algoritm funcționează în timp cvasiliniar dacă T ( n ) = O ( n log ^k n ) pentru orice constantă k ; timpul liniaritmic este cazul k = 1. Algoritmii de timp cvasi-liniari sunt de asemenea o ( n ^{1+ ε} ) pentru fiecare ε > 0 și funcționează mai repede decât orice polinom din n cu exponent strict mai mare de 1.

Algoritmii care rulează în timp cvasiliniar, pe lângă algoritmii liniaritmici enumerați mai sus, includ:

Sortare de îmbinare la loc , O ( n log ² n )

Timp subcadratic

Se spune că un algoritm se află în timp subcadratic dacă T ( n ) = o ( n ² ).

De exemplu, majoritatea algoritmilor de sortare naivi , bazate pe comparații, sunt pătratici (de exemplu, inserați sortarea ), dar puteți găsi algoritmi mai avansați care sunt subquadratici (de exemplu, sortarea Shell ). Nici o sortare polivalentă nu se face în timp liniar, dar schimbarea de la pătratic la subquadratic are o mare importanță fiscală.

Timp polinomial

Se spune că un algoritm este în timp polinomial dacă timpul său de execuție este delimitat în partea superioară de o expresie polinomială în dimensiunea intrării în algoritm, adică T ( n ) = O ( n ^k ) pentru o constantă k . ^[1] ^[6] Problemele pentru care există un algoritm determinist în timp polinomial aparțin clasei de complexitate P , care este centrală în domeniul teoriei complexității de calcul . Teza lui Cobham afirmă că timpul polinomial este un sinonim pentru „tratabil”, „fezabil”, „eficient” sau „rapid”. ^[7]

Câteva exemple de algoritmi polinomiali de timp:

Algoritmul de sortare rapid pe n numere întregi este cel mai performant $An^{2}$ ${\ displaystyle An ^ {2}}$ ${\ displaystyle An ^ {2}}$ operații pentru unele constante A. Prin urmare, se efectuează în timp polinomial $O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ și este un algoritm de timp polinomial.
Toate operațiile aritmetice de bază (adunare, scădere, înmulțire, divizare și comparație) se pot face în timp polinomial.
Încadrările maxime în grafice pot fi găsite în timp polinomial.

Timp puternic și slab polinomial

În unele contexte, în special în optimizare , se diferențiază algoritmii în timp puternic polinomial și în timp slab polinomial . Aceste două concepte sunt relevante numai dacă intrările în algoritmi constau din numere întregi.

Timpul puternic polinomial este definit în modelul aritmetic de calcul. În acest model de calcul, operațiile aritmetice de bază (adunare, scădere, multiplicare, împărțire și comparație) fac un pas în unitatea de timp care trebuie efectuată, indiferent de mărimea operanzilor. Algoritmul execută un timp puternic polinomial dacă ^[8]

numărul de operații din modelul aritmetic de calcul este limitat de un polinom în numărul de numere întregi ale instanței de intrare; Și
spațiul utilizat de algoritm este limitat de un polinom în dimensiunea intrării.

Orice algoritm cu aceste două proprietăți poate fi convertit într-un algoritm de timp polinomial prin înlocuirea operațiilor aritmetice cu algoritmi adecvați pentru efectuarea operațiilor aritmetice pe o mașină Turing . Dacă a doua dintre cerințele de mai sus nu este îndeplinită, atunci acest lucru nu mai este adevărat. Având în vedere întregul $2^{n}$ ${\ displaystyle 2 ^ {n}}$ $2 ^ {n}$ (care ocupă un spațiu proporțional cu n ), este posibil să se calculeze $2^{2^{n}}$ ${\ displaystyle 2 ^ {2 ^ {n}}}$ ${\ displaystyle 2 ^ {2 ^ {n}}}$ cu n multiplicări folosind cvadratură repetată . Cu toate acestea, spațiul folosit pentru a reprezenta $2^{2^{n}}$ ${\ displaystyle 2 ^ {2 ^ {n}}}$ ${\ displaystyle 2 ^ {2 ^ {n}}}$ este proporțional cu $2^{n}$ ${\ displaystyle 2 ^ {n}}$ $2 ^ {n}$ , și deci exponențial mai degrabă decât polinomial în spațiul folosit pentru a reprezenta intrarea. Prin urmare, nu este posibil să se efectueze acest calcul în timp polinomial într-o mașină Turing, dar este posibil să se calculeze polinomial prin multe operații aritmetice.

În schimb, există algoritmi care sunt efectuați în mai multe etape ale mașinii Turing limitate de un polinom în ceea ce privește lungimea intrării în cod binar, dar nu utilizează un număr de operații aritmetice limitate de un polinom în ceea ce privește numărul de numerele de intrare. Algoritmul euclidian pentru calcularea celui mai mare divizor comun al a două numere întregi este un exemplu. Având în vedere două numere întregi $la$ ${\ displaystyle a}$ $la$ Și $b$ ${\ displaystyle b}$ $b$ timpul de execuție al algoritmului este limitat de $O((\log \ a+\log \ b)^{2})$ ${\ displaystyle O ((\ log \ a + \ log \ b) ^ {2})}$ ${\ displaystyle O ((\ log \ a + \ log \ b) ^ {2})}$ treptele mașinii Turing. Acesta este polinom în mărimea unei reprezentări binare a $la$ ${\ displaystyle a}$ $la$ Și $b$ ${\ displaystyle b}$ $b$ întrucât dimensiunea acestei reprezentări este aproximativă $\log \ a+\log \ b$ ${\ displaystyle \ log \ a + \ log \ b}$ ${\ displaystyle \ log \ a + \ log \ b}$ . În același timp, numărul de operații aritmetice nu poate fi limitat de numărul de numere întregi din intrare (care este constant în acest caz: există întotdeauna doar două numere întregi în intrare). Datorită acestei ultime observații, algoritmul nu funcționează în timp strict polinomial. Durata sa efectivă de funcționare depinde de amplitudinile $la$ ${\ displaystyle a}$ $la$ Și $b$ ${\ displaystyle b}$ $b$ și nu doar numărul de numere întregi din intrare.

Un algoritm care rulează în timp polinomial, dar care nu este puternic polinomial, se spune că rulează în timp slab polinomial . ^[9] Un exemplu bine cunoscut al unei probleme pentru care este cunoscut un algoritm de timp slab polinomial, dar nu se știe dacă admite un algoritm de timp puternic polinomial, este programarea liniară . Timpul slab polinomial nu trebuie confundat cu timpul pseudopolinomial .

Clasele de complexitate

Conceptul de timp polinomial conduce la diverse clase de complexitate în teoria complexității de calcul. Unele clase importante definite folosind timpul polinomial sunt următoarele.

P : Clasa de complexitate a problemelor de decizie care pot fi rezolvate pe o mașină Turing deterministă în timp polinomial.
NP : Clasa de complexitate a problemelor de decizie care pot fi rezolvate pe o mașină Turing nedeterministă în timp polinomial.
ZPP : Clasa de complexitate a problemelor de decizie care pot fi rezolvate cu eroare zero pe o mașină probabilistică Turing în timp polinomial.
RP : Clasa de complexitate a problemelor de decizie care pot fi rezolvate cu o eroare unilaterală pe o mașină probabilistică Turing în timp polinomial.
BPP : Clasa de complexitate a problemelor de decizie care pot fi rezolvate cu o eroare față-verso pe o mașină probabilistică Turing în timp polinomial.
BQP : Clasa de complexitate a problemelor de decizie care pot fi rezolvate cu o eroare față-verso pe o mașină cuantică Turing în timp polinomial.

P este cea mai mică clasă de complexitate temporală pe o mașină deterministă, care este robustă în ceea ce privește modificările modelului de mașină. (De exemplu, o schimbare de la o singură panglică mașină Turing la o mașină multi-panglică poate duce la o creștere a vitezei pătratică, dar orice algoritm , care funcționează în timp polinomial bazat pe un model face acest lucru pe de altă parte.) Orice dată mașină abstractă va avea o clasă de complexitate corespunzătoare problemelor care pot fi rezolvate în timp polinomial pe acea mașină.

Timpul superpolinomial

Se spune că un algoritm necesită timp superpolinomial dacă T ( n ) nu este delimitat mai sus de niciun polinom. Este timpul ω ( n ^c ) pentru toate constantele c , unde n este parametrul de intrare, de obicei numărul de biți din intrare.

De exemplu, un algoritm care rulează pentru 2 ⁿ pași pe o intrare de dimensiunea n necesită timp superpolinomial (mai exact, timp exponențial).

Un algoritm care utilizează resurse exponențiale este clar superpolinomial, dar unii algoritmi sunt doar foarte slab superpolinomiali. De exemplu, testul de primărie Adleman-Pomerance-Rumely se efectuează pentru un timp n ^{O (log log n )} la intrări de n biți; acest lucru crește mai repede decât orice polinom pentru n suficient de mare, dar dimensiunea intrării trebuie să devină nerealistă înainte ca un polinom de grad mic să nu-l mai poată domina.

Un algoritm care necesită timp superpolinomial se află în afara clasei de complexitate P. Teza lui Cobham postulează că acești algoritmi sunt impracticabili și, în multe cazuri, sunt. Deoarece problema P versus NP este nerezolvată, nu se cunoaște în prezent niciun algoritm pentru o problemă NP-completă care funcționează în timp polinomial.

Timp cvasi-polinomial

Algoritmii de timp cvasi-polinomiali sunt algoritmi care rulează mai lent decât timpul polinomial, dar nu atât de încet încât să fie timp exponențial. Cel mai rău timp de execuție al unui algoritm de timp cvasi-polinomial este $2^{O((\log n)^{c})}$ ${\ displaystyle 2 ^ {O ((\ log n) ^ {c})}}$ ${\ displaystyle 2 ^ {O ((\ log n) ^ {c})}}$ pentru unele fixe c . Cel mai cunoscut algoritm clasic pentru factorizarea numerelor întregi, situl câmpurilor numerice generale , care se efectuează într-un timp de aproximativ $2^{{\tilde {O}}(n^{1/3})}$ ${\ displaystyle 2 ^ {{\ tilde {O}} (n ^ {1/3})}}$ ${\ displaystyle 2 ^ {{\ tilde {O}} (n ^ {1/3})}}$ nu este cvasi-polinom, deoarece timpul de execuție nu poate fi exprimat ca $2^{O((\log n)^{c})}$ ${\ displaystyle 2 ^ {O ((\ log n) ^ {c})}}$ ${\ displaystyle 2 ^ {O ((\ log n) ^ {c})}}$ pentru unele fixe c . Dacă constanta c din definiția algoritmilor de timp cvasi-polinomiali este egală cu 1, obținem un algoritm de timp polinomial și dacă este mai mic de 1, obținem un algoritm de timp sub-liniar.

Algoritmii de timp aproape polinomiali apar de obicei în reduceri de la o problemă NP-hard la o altă problemă. De exemplu, puteți lua instanța unei probleme NP dificile, să spunem 3SAT și să o convertiți într-o instanță a unei alte probleme B, dar dimensiunea instanței devine $2^{O((\log n)^{c})}$ ${\ displaystyle 2 ^ {O ((\ log n) ^ {c})}}$ ${\ displaystyle 2 ^ {O ((\ log n) ^ {c})}}$ . În acest caz, această reducere nu dovedește că problema B este NP-dificilă; această reducere arată doar că nu există un algoritm polinomial pentru B, cu excepția cazului în care există un algoritm cvasi-polinomial pentru 3SAT (și așa pentru toate NP-urile ). În mod similar, există unele probleme pentru care cunoaștem algoritmi de timp cvasi polinomiali, dar nu se cunoaște niciun algoritm de timp polinomial. Astfel de probleme apar în algoritmi de aproximare; un exemplu celebru este problema arborelui Steiner , pentru care există un algoritm de aproximare în timp cvasi-polinomial care realizează un factor de aproximare de $O(\log ^{3}n)$ ${\ displaystyle O (\ log ^ {3} n)}$ ${\ displaystyle O (\ log ^ {3} n)}$ ( n fiind numărul de vârfuri), dar demonstrarea existenței unui astfel de algoritm în timp polinomial este o problemă deschisă

Clasa de complexitate QP constă din toate problemele care au algoritmi de timp cvasi-polinomiali. Poate fi definit în termeni DTIME după cum urmează. ^[10]

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

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

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

Relația cu problemele NP-complete

În teoria complexității, problema nerezolvată P versus NP întreabă dacă toate problemele din NP au algoritmi polinomiali de timp. Toți algoritmii binecunoscuți pentru probleme NP-complete , cum ar fi 3SAT și altele, iau timp exponențial. Într-adevăr, este presupus pentru multe probleme naturale NP-complete că, în cazul în care avem algoritmi de timp subexponențiali. Aici "timp subexponențial" se presupune că înseamnă a doua definiție prezentată mai sus. (Pe de altă parte, multe probleme ale graficelor reprezentate în mod natural de matricile de adiacență sunt rezolvabile în timp subexponențial pur și simplu pentru că dimensiunea intrării este pătratul numărului de vârfuri.) Această conjectură (pentru problema k -SAT) este cunoscută sub numele de ipoteza exponențială a timpului . ^[11] Deoarece se presupune că problemele NP-complete nu au algoritmi de timp cvasi-polinomiali, unele rezultate de aproximare în domeniul algoritmilor de aproximare fac presupunerea că problemele NP-complete nu au algoritmi de timp cvasi-polinomiali. De exemplu, consultați rezultatele de aproximare cunoscute pentru problema de acoperire setată .

Timp subexponențial

Termenul de timp subexponențial este folosit pentru a exprima faptul că timpul de execuție al unui algoritm poate crește mai repede decât orice polinom, dar este încă semnificativ mai mic decât un exponențial. În acest sens, problemele care au algoritmi de timp subexponențiali sunt oarecum mai tratabile decât cele care au doar algoritmi exponențiali. În general, nu există un acord cu privire la definiția precisă a „subexponențialului” ^[12] și enumerăm cele două cele mai utilizate pe scară mai jos.

Prima definiție

Se spune că o problemă poate fi rezolvată în timp subexponențial dacă poate fi rezolvată în timpi de execuție ale căror logaritmi cresc mai puțin decât orice polinom dat. Mai precis, o problemă este în timp subexponențial dacă pentru fiecare ε > 0 există un algoritm care rezolvă problema în timpul 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)

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

{\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, ilcrivello dei campi di numeri generale , che funziona nel tempo di circa $2^{{\tilde {O}}(n^{1/3})}$ $2^{{\tilde {O}}(n^{1/3})}$ $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)$ ${\displaystyle (L,k)}$ $(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).

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

{\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)$ ${\displaystyle (L,k)}$ $(L,k)$ per i quali vi è una funzione computabile $f:\mathbb {N} \to \mathbb {N}$ $f:\mathbb {N} \to \mathbb {N}$ $f:\mathbb {N} \to \mathbb {N}$ con $f\in o(k)$ $f\in o(k)$ $f\in o(k)$ e un algoritmo che decide L nel tempo $2^{f(k)}\cdot {\text{poly}}(n)$ $2^{f(k)}\cdot {\text{poly}}(n)$ $2^{f(k)}\cdot {\text{poly}}(n)$ .

Ipotesi del tempo esponenziale

Lo stesso argomento in dettaglio: 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 k SAT 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)

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

{\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)

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

{\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}}})

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

{\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 JE 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 ) .
^ PB 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 .
^ 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

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 JE 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] PB 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 .

[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]