Complexitatea algoritmului în medie

În teoria complexității computaționale , complexitatea medie a unui algoritm  este cantitatea de resurse de calcul (de obicei, timp) necesară pentru ca algoritmul să funcționeze, mediată pentru toate intrările posibile. Conceptul este adesea contrastat cu cel mai rău caz de complexitate , unde este luată în considerare complexitatea maximă a unui algoritm pentru toate intrările.

Există trei motive principale pentru studierea complexității în medie [1] . În primul rând, în timp ce unele probleme pot fi dificil de rezolvat în cel mai rău caz, intrările care duc la acest comportament sunt rare în practică, astfel încât complexitatea în medie poate fi o măsură mai precisă a performanței unui algoritm. În al doilea rând, analiza complexității oferă, în medie, un mijloc și o tehnică pentru generarea de date complexe pentru o problemă, care pot fi utilizate în criptare și derandomizare . În al treilea rând, complexitatea permite, în medie, să evidențiem cel mai eficient algoritm în practică dintre algoritmii de aceeași complexitate subiacentă (cum ar fi quicksort ).

Analiza algoritmilor necesită în medie noțiunea de date „medie” a algoritmului, ceea ce duce la problema gândirii prin distribuția de probabilitate a datelor de intrare. Se poate folosi și un algoritm probabilistic . Analiza unor astfel de algoritmi conduce la noțiunea aferentă complexității așteptate [2] .

Istorie și fundal

Performanța algoritmilor în medie a fost studiată încă de la introducerea noțiunilor moderne de eficiență computațională în anii 1950. Majoritatea lucrărilor inițiale s-au concentrat pe probleme pentru care erau cunoscuți algoritmi de timp polinomial în cel mai rău caz [3] . În 1973 , Donald Knuth [4] a publicat al treilea volum din The Art of Computer Programming , în care a oferit o privire de ansamblu asupra performanței în medie a algoritmilor pentru probleme care pot fi rezolvate în timp polinomial în cel mai rău caz, cum ar fi sortarea. și calculul medianei .

Un algoritm eficient pentru probleme NP-complete presupune, în general, că rulează în timp polinomial pentru toate intrările, ceea ce este echivalent cu complexitatea în cel mai rău caz. Cu toate acestea, un algoritm care este ineficient pe o cantitate „mică” de date poate fi destul de eficient pe „majoritatea” datelor întâlnite în practică. Astfel, este de dorit să se studieze proprietățile algoritmilor pentru care complexitatea în medie poate diferi semnificativ de complexitatea în cel mai rău caz.

Conceptele fundamentale ale complexității medii au fost dezvoltate de Levin, Leonid Anatolyevich , care a publicat un articol de o pagină [5] în 1986 , în care a definit complexitatea și completitudinea medie, dând un exemplu de problemă completă a clasei distNP, un analog. de NP-completitudine pentru complexitate medie.

Definiții

Algoritm eficient mediu

Primul obiectiv este de a defini exact ceea ce înseamnă că algoritmul este eficient „în medie”. Se poate încerca să se definească un algoritm eficient mediu ca un algoritm a cărui valoare așteptată este polinomială pentru toate intrările posibile. Această definiție are diverse dezavantaje. În special, această definiție nu este stabilă în ceea ce privește modificările în modelul de calcul (de exemplu, când se înlocuiește o mașină Turing cu mai multe benzi cu una cu o singură bandă). Fie, de exemplu, algoritmul A rulat în timpul t A (x) pe intrarea x și algoritmul B rulează în timpul t A (x) 2 pe intrarea x. Adică, B este pătratic mai lent decât A. Este intuitiv clar că orice definiție a eficienței medii trebuie să folosească ideea că A este eficientă medie dacă și numai dacă B este eficientă medie. Să presupunem, totuși, că intrarea este luată aleatoriu din șiruri uniform distribuite de lungime n și că A rulează în timp n 2 pe toate intrările cu excepția șirului 1 n , care necesită timp 2 n . Este ușor să verifici acel covor. așteptarea timpului de rulare al algoritmului A este polinomială, dar mat. așteptarea algoritmului B este exponențială [3] .

Pentru a crea o definiție mai puternică a eficienței medii, este logic să lăsăm A să ruleze în timp mai mult decât polinomial pe unele intrări, dar fracțiunea de date pentru care A durează din ce în ce mai mult timp va deveni din ce în ce mai mică. Această idee este surprinsă în următoarea formulă pentru timpul mediu de rulare polinom, în care timpul de rulare și fracția de intrare sunt echilibrate:

pentru orice n, t, ε > 0 și polinom p, unde t A (x) înseamnă timpul de rulare al algoritmului A la intrarea x [6] . Alternativ, poate fi scris după cum urmează

pentru o constantă C, unde n = |x| [7] . Cu alte cuvinte, algoritmul A are o complexitate medie bună dacă după t A (n) pașii A pot rezolva toate problemele, cu excepția unei fracțiuni de probleme cu lungimea de intrare n, pentru unele ε, c > 0 [3] .

Probleme cu distribuțiile cunoscute

Următorul pas este de a determina intrarea „medie” pentru o anumită sarcină. Acest lucru se realizează prin asocierea intrării fiecărei sarcini cu o anumită distribuție de probabilitate. Adică problema „medie” constă din limbajul L (adică un set de cuvinte reprezentând datele de intrare) și distribuția D asociată acestuia, rezultând o pereche (L, D) (o problemă cu distribuții cunoscute) [7] . Cele mai comune două clase de distribuție de probabilitate sunt:

  1. Distribuțiile calculabile în timp polinomial (P-calculabile) sunt distribuții pentru care poate fi calculată densitatea sumă a oricărei intrări date x. Formal, având în vedere o distribuție μ și un rând x ∈ {0, 1} n , se poate calcula valoarea în timp polinomial. De aici rezultă că Pr[x] este de asemenea calculabil în timp polinomial.
  2. Distribuțiile polinom-constructibile în timp (P-constructibile) sunt distribuții care pot fi eșantionate aleatoriu în timp polinomial.

Cele două concepte nu sunt echivalente, deși sunt similare. Dacă o distribuție este P-calculabilă, este și P-constructibilă, dar inversul nu este adevărat dacă P ≠ P #P [7] .

AvgP și distNP

O problemă cu distribuțiile cunoscute (L, D) aparține clasei de complexitate AvgP dacă există un algoritm eficient mediu pentru L așa cum este definit mai sus. Clasa AvgP este uneori denumită în literatură distP [7] .

O problemă cu distribuții cunoscute (L, D) aparține clasei de complexitate distNP dacă L aparține lui NP și D este P-calculabil. Dacă L aparține lui NP și D este P-constructibil, atunci (L, D) aparține sampNP [7] .

Două clase, AvgP și distNP, definesc o analogie a lui P și respectiv NP de complexitate medie [7] .

Reductibilitatea problemelor cu distribuțiile cunoscute

Fie (L,D) și (L',D') două probleme cu distribuții cunoscute. (L, D) se reduce în medie la (L', D') (scris (L, D) ≤ AvgP (L', D')) dacă există o funcție f astfel încât pentru orice n poate fi calculată la intrarea x în timp polinomial în n și

  1. (Corectitatea) x ∈ L dacă și numai dacă f(x) ∈ L'
  2. (Dominație) Există polinoame p și m astfel încât pentru orice n și y,

Condiția de dominanță conduce la ideea că dacă problema (L, D) este grea în medie, atunci (L', D') este, de asemenea, grea în medie. Intuitiv, reducerea ar trebui să ofere o modalitate de a rezolva problema L pentru intrarea x prin calculul f(x) și să alimenteze rezultatul algoritmului la algoritmul care rezolvă L'. Fără o condiție de dominanță, acest lucru s-ar putea să nu fie posibil, deoarece un algoritm care rezolvă L în timp polinomial în medie poate rula în timp superpolinom pentru un număr mic de intrări, dar aceste intrări pot fi mapate la o mulțime mare în D', deci algoritmul A' în timp polinomial în timp mediu nu va funcționa. Condiția de dominanță specifică că astfel de rânduri vor apărea în D' polinomial adesea [6] .

Sarcini DistNP-complete

Analogia de complexitate medie pentru complexitatea NP este distNP-completitudinea. O problemă cu distribuțiile cunoscute (L’, D’) este distNP-complet dacă (L’, D’) aparține distNP și orice (L, D) din distNP (în complexitate medie) este reductibilă la (L’, D’). ) [ 7] .

Un exemplu de problemă distNP-completă este problema de oprire restricționată , BH, definită după cum urmează:

BH = {(M,x,1 t ) : M este o mașină Turing nedeterministă care ia x în ≤ t pași [7] .

În lucrarea sa, Levin a arătat un exemplu de problemă de tiling care este în medie NP-complet [5] . O prezentare generală a problemelor distNP-complete cunoscute poate fi găsită în cartea lui Wang [6] .

Cercetare activă este în desfășurare în căutarea de noi probleme distNP-complete. Totuși, găsirea unor astfel de probleme poate fi dificilă din cauza rezultatului lui Gurevich, care a arătat că orice problemă cu distribuțiile cunoscute nu poate fi distNP-completă decât dacă EXP = NEXP [8] . (Distribuția uniformă μ este una dintre distribuțiile pentru care există ε > 0 astfel încât pentru orice x μ(x) ≤ 2 -|x| ε .) Rezultatul lui Livne arată că toate problemele NP naturale au o versiune DistNP-completă [ 9] . Totuși, scopul de a găsi probleme de distribuție naturale care sunt DistNP-complete nu a fost atins [10] .

Aplicații

Algoritmi de sortare

După cum sa menționat mai sus, o mare parte din lucrările timpurii privind complexitatea medie s-au concentrat pe probleme pentru care erau cunoscuți algoritmi de timp polinomial, cum ar fi sortarea. De exemplu, mulți algoritmi de sortare, cum ar fi quicksort , au un timp de rulare în cel mai rău caz de O(n 2 ), dar un timp de rulare mediu de O(nlog(n)), unde n este lungimea datelor sortate [ 11] .

Criptografie

Pentru majoritatea problemelor, analiza complexității medii a fost efectuată pentru a găsi algoritmi eficienți pentru o problemă care este considerată dificilă ca complexitate în cel mai rău caz. În criptografie, totuși, opusul este adevărat – complexitatea este în cel mai rău caz lipsită de importanță; în schimb, dorim să garantăm că orice algoritm complex, în medie, care „rupe” o schemă criptografică, este ineficient [12] .

Astfel, toate schemele criptografice se bazează pe existența unor funcții unidirecționale [3] . Deși existența funcțiilor unidirecționale rămâne o problemă deschisă, mulți candidați pentru funcții unidirecționale se bazează pe probleme dificile, cum ar fi factorizarea întregilor sau calcularea logaritmului discret . Rețineți că nu este de dorit ca o funcție candidată să fie NP-completă, deoarece acest lucru asigură doar că nu există un algoritm eficient pentru complexitatea cazului cel mai rău. De fapt, vrem să ne asigurăm că nu există un algoritm eficient care să rezolve problema pentru intrări aleatorii (adică în complexitate în medie). De fapt, atât problema factorizării numerelor întregi, cât și problema calculării logaritmului discret aparțin lui NP ∩ coNP , și de aceea nu se crede că acestea sunt NP-complete [7] . Faptul că toată criptografia se bazează pe existența unor probleme greu de rezolvat în medie în NP este unul dintre principalele motive pentru studierea complexității în medie.

Alte rezultate

În 1990, Impagliazzo și Levin au arătat că, dacă există un algoritm eficient mediu pentru o problemă distNP-completă sub distribuție uniformă, atunci există un algoritm eficient mediu pentru orice problemă din NP pentru orice distribuție construită în timp polinomial [13] . Aplicarea acestei teorii la problemele cu distribuții naturale cunoscute rămâne o întrebare deschisă [3] .

În 1992, Ben-David și colab. au arătat că, dacă toate limbile din distNP au algoritmi de decizie medii buni , au algoritmi de căutare medii buni. Mai mult, ei au arătat că acest lucru este valabil și în cazul unor ipoteze mai slabe - dacă orice limbaj din NP este simplu în medie pentru algoritmii de selecție în distribuție uniformă, atunci va fi, de asemenea, mediu simplu pentru algoritmii de căutare sub distribuție uniformă [14] . Astfel, funcțiile criptografice unidirecționale pot exista doar dacă există probleme de la distNP pe o distribuție uniformă care sunt dificile în medie pentru algoritmii de decizie .

În 1993, Feigenbaum și Fortnow au arătat că este imposibil să se demonstreze, în cazul reducerii aleatoare neadaptative, că existența unui algoritm mediu bun pentru o problemă distNP-completă sub distribuție uniformă implică existența unui algoritm eficient în cel mai rău caz în NP. [15] . În 2003, Bogdanov și Trevisan au generalizat acest rezultat la o reducere arbitrară neadaptativă [16] . Acest rezultat arată că este greu posibil să se găsească o relație între complexitatea medie și complexitatea celui mai rău caz folosind reducerea [3] .

Vezi și

Note

  1. ↑ Goldreich, Vadhan, 2007 , p. 325–330.
  2. ↑ Cormen, Leiserson, Rivest, Stein, 2009 , p. 28.
  3. ↑ 1 2 3 4 5 6 Bogdanov și Trevisan, 2006 , p. 1–106.
  4. ↑ Knuth, 1973 .
  5. ↑ 12 Levin , 1986 , p. 285–286.
  6. ↑ 1 2 3 Wang, 1997 , p. 295–328.
  7. ↑ 1 2 3 4 5 6 7 8 9 Arora, Barak, 2009 .
  8. ↑ Gurevici, 1987 , p. 111–117.
  9. ↑ Livene, 2006 .
  10. ↑ Goldreich, 1997 .
  11. ↑ Cormen, Leiserson, Rivest, Stein, 2009 .
  12. ↑ Katz, Lindell, 2007 .
  13. ↑ Impagliazzo și Levin 1990 , p. 812–821.
  14. ↑ Ben-David, Chor, Goldreich, Luby, 1992 , p. 193–219.
  15. ↑ Feigenbaum, Fortnow, 1993 , p. 994–1005.
  16. ↑ Bogdanov, Trevisan, 2003 , p. 308–317.

Literatură

Lectură suplimentară