Complexitate medie-caz - Average-case complexity

În teoria complexității computaționale , medie caz complexitatea unui algoritm este cantitatea unor resurse de calcul ( de obicei , timp) utilizat de algoritmul, în medie pe toate intrările posibile. Este frecvent contrastat cu cel mai rău caz de complexitate, care ia în considerare complexitatea maximă a algoritmului pentru toate intrările posibile.

Există trei motivații principale pentru studierea complexității medii a cazurilor. În primul rând, deși unele probleme pot fi insolvabile în cel mai rău caz, intrările care determină acest comportament pot să apară rar în practică, astfel încât complexitatea cazului mediu poate fi o măsură mai precisă a performanței unui algoritm. În al doilea rând, analiza complexității cazurilor medii oferă instrumente și tehnici pentru a genera instanțe dificile de probleme care pot fi utilizate în domenii precum criptografie și derandomizare . În al treilea rând, complexitatea cazurilor medii permite discriminarea algoritmului cel mai eficient din practică între algoritmii cu complexitate echivalentă a cazului cel mai bun (de exemplu Quicksort ).

Analiza cazului mediu necesită o noțiune de intrare „medie” la un algoritm, ceea ce duce la problema conceperii unei distribuții de probabilitate peste intrări. Alternativ, poate fi utilizat un algoritm randomizat . Analiza unor astfel de algoritmi duce la noțiunea conexă a unei complexități așteptate .

Istorie și fundal

Performanța medie-caz a algoritmilor a fost studiată de când noțiunile moderne de eficiență de calcul au fost dezvoltate în anii 1950. O mare parte din această lucrare inițială s-a concentrat pe probleme pentru care algoritmii polinomiali în cel mai rău caz erau deja cunoscuți. În 1973, Donald Knuth a publicat Volumul 3 al Art of Computer Programming care analizează pe larg performanța cazurilor medii a algoritmilor pentru probleme rezolvabile în cel mai rău caz polinomial, cum ar fi sortarea și găsirea mediană.

Un algoritm eficient pentru problemele NP-complete este în general caracterizat ca unul care rulează în timp polinomial pentru toate intrările; acest lucru este echivalent cu necesitatea unei complexități eficiente în cel mai rău caz. Cu toate acestea, un algoritm care este ineficient pentru un număr „mic” de intrări poate fi în continuare eficient pentru „majoritatea” intrărilor care apar în practică. Astfel, este de dorit să se studieze proprietățile acestor algoritmi în care complexitatea medie a cazurilor poate diferi de cea mai gravă și să se găsească metode pentru a le raporta pe cele două.

Noțiunile fundamentale de complexitate a cazului mediu au fost dezvoltate de Leonid Levin în 1986, când a publicat o lucrare de o pagină care definește complexitatea și completitudinea cazului mediu, oferind în același timp un exemplu de problemă completă pentru distNP, analogul cazului mediu al NP .

Definiții

Complexitate eficientă a cazului mediu

Prima sarcină este de a defini cu exactitate ce se înțelege prin algoritm care este eficient „în medie”. O încercare inițială ar putea defini un algoritm eficient de caz mediu ca unul care rulează în timpul polinomului așteptat pe toate intrările posibile. O astfel de definiție are diferite neajunsuri; în special, nu este robust la schimbările modelului de calcul. De exemplu, să presupunem că algoritmul A rulează în timpul t _A (x) pe intrarea x și algoritmul B rulează în timpul t _A (x) ² pe intrarea x; adică, B este de patru ori mai lent decât A. Intuitiv, orice definiție a eficienței medii a cazurilor ar trebui să surprindă ideea că A este eficientă în medie dacă și numai dacă B este eficientă în medie. Să presupunem, totuși, că intrările sunt trase aleatoriu din distribuția uniformă a șirurilor cu lungimea și că A rulează în timpul n ² pe toate intrările, cu excepția șirului 1 ⁿ pentru care A durează 2 ⁿ . Apoi se poate verifica cu ușurință dacă timpul de funcționare așteptat al lui A este polinomial, dar timpul de funcționare așteptat al lui B este exponențial. ${\ displaystyle n}$

Pentru a crea o definiție mai robustă a eficienței medii a cazurilor, este logic să permiteți algoritmului A să ruleze mai mult decât timpul polinomial pe unele intrări, dar fracțiunea de intrări pe care A necesită un timp de funcționare din ce în ce mai mare devine din ce în ce mai mică. Această intuiție este surprinsă în următoarea formulă pentru timpul mediu de rulare polinomial, care echilibrează compromisul polinomial între timpul de rulare și fracția de intrări:

${\ displaystyle \ Pr _ {x \ in _ {R} D_ {n}} \ left [t_ {A} (x) \ geq t \ right] \ leq {\ frac {p (n)} {t ^ { \ epsilon}}}}$

pentru fiecare n, t, ε> 0 și polinomul p, unde t _A (x) denotă timpul de funcționare al algoritmului A la intrarea x. Alternativ, acest lucru poate fi scris ca

${\ displaystyle E_ {x \ in _ {R} D_ {n}} \ left [{\ frac {t_ {A} (x) ^ {\ epsilon}} {n}} \ right] \ leq C}$

pentru o constantă C, unde n = | x |. Cu alte cuvinte, un algoritm A are o bună complexitate medie-caz dacă, după ce rulează pentru pași t _A (n), A poate rezolva toate, cu excepția unei fracțiuni din intrările de lungime n, pentru unele ε, c> 0. ${\ displaystyle {\ frac {n ^ {c}} {(t_ {A} (n)) ^ {\ epsilon}}}}$

Problemă de distribuție

Următorul pas este de a defini intrarea „medie” la o anumită problemă. Acest lucru se realizează prin asocierea intrărilor fiecărei probleme cu o anumită distribuție de probabilitate. Adică, o problemă de „caz mediu” constă dintr-un limbaj L și o distribuție de probabilitate asociată D care formează perechea (L, D). Cele mai comune două clase de distribuții permise sunt:

1. Distribuții computabile în timp polinomial (P-calculabile): acestea sunt distribuții pentru care este posibil să se calculeze densitatea cumulativă a oricărei intrări date x. Mai formal, având în vedere o distribuție de probabilitate μ și un șir x ∈ {0, 1} ⁿ este posibil să se calculeze valoarea în timp polinomial. Aceasta implică faptul că Pr [x] este, de asemenea, calculabil în timp polinomial.${\ displaystyle \ mu (x) = \ sum \ limits _ {y \ in \ {0,1 \} ^ {n}: y \ leq x} \ Pr [y]}$
2. Distribuții eșantionabile în timp polinomial (P-eșantionabil): acestea sunt distribuții din care este posibil să se extragă probe aleatorii în timp polinomial.

Aceste două formulări, deși similare, nu sunt echivalente. Dacă o distribuție este P-calculabilă, este și P-eșantionabilă, dar inversul nu este adevărat dacă P ≠ P ^#P .

AvgP și distNP

O problemă de distribuție (L, D) se află în clasa de complexitate AvgP dacă există un algoritm eficient de caz mediu pentru L, așa cum s-a definit mai sus. Clasa AvgP este denumită ocazional distP în literatură.

O problemă de distribuție (L, D) este în clasa de complexitate distNP dacă L este în NP și D este P-calculabil. Când L este în NP și D este P-eșantionabil, (L, D) aparține sampNP.

Împreună, AvgP și distNP definesc analogii de caz medii ai P, respectiv NP.

Reduceri între problemele de distribuție

Fie (L, D) și (L ', D') două probleme de distribuție. (L, D) cazul mediu se reduce la (L ', D') (scris (L, D) ≤ _AvgP (L ', D')) dacă există o funcție f care pentru fiecare n, la intrarea x poate fi calculat în timp polinom în n și

1. (Corectitudine) x ∈ L dacă și numai dacă f (x) ∈ L '
2. (Dominație) Există polinoame p și m astfel încât, pentru fiecare n și y, ${\ displaystyle \ sum \ limits _ {x: f (x) = y} D_ {n} (x) \ leq p (n) D '_ {m (n)} (y)}$

Condiția de dominație impune noțiunea că dacă problema (L, D) este dificilă în medie, atunci (L ', D') este, de asemenea, dificilă în medie. Intuitiv, o reducere ar trebui să ofere o modalitate de a rezolva o instanță x a problemei L calculând f (x) și alimentând ieșirea către algoritmul care rezolvă L '. Fără condiția de dominație, acest lucru ar putea să nu fie posibil, deoarece algoritmul care rezolvă L în timp polinomial poate lua timp super-polinomial pe un număr mic de intrări, dar f poate asocia aceste intrări într-un set mult mai mare de D ', astfel încât algoritmul A 'nu mai rulează în timp polinomial în medie. Condiția de dominație permite ca astfel de șiruri să apară polinomial la fel de des în D '.

Probleme complete DistNP

Analogul de caz mediu al completitudinii NP este distNP-completitudinea. O problemă de distribuție (L ', D') este distNP-completă dacă (L ', D') este în distNP și pentru fiecare (L, D) în distNP, (L, D) este reductibil în caz mediu la (L ') , D ').

Un exemplu de problemă distNP-completă este Bounded Halting Problem, BH, definită după cum urmează:

BH = {(M, x, 1 ^t ): M este o mașină de Turing nedeterministă care acceptă x în ≤ t pași.}

În lucrarea sa originală, Levin a arătat un exemplu al unei probleme de distribuție a plăcilor care este NP completă în caz mediu. Un sondaj al problemelor cunoscute distNP-complete este disponibil online.

Un domeniu de cercetare activă implică găsirea de noi probleme distNP-complete. Cu toate acestea, găsirea unor astfel de probleme poate fi complicată datorită rezultatului Gurevich, care arată că orice problemă de distribuție cu o distribuție plană nu poate fi completă distNP decât dacă EXP = NEXP . (O distribuție plană μ este una pentru care există un ε> 0 astfel încât pentru orice x, μ (x) ≤ 2 ^{- | x | ε} .) Un rezultat al lui Livne arată că toate problemele naturale NP-complete au DistNP-complete versiuni. Cu toate acestea, obiectivul de a găsi o problemă naturală de distribuție care este DistNP-complet nu a fost încă atins.

Aplicații

Algoritmi de sortare

Așa cum s-a menționat mai sus, multe lucrări timpurii referitoare la complexitatea cazurilor medii s-au concentrat pe probleme pentru care existau deja algoritmi de timp polinomial, cum ar fi sortarea. De exemplu, mulți algoritmi de sortare care utilizează aleatoriu, cum ar fi Quicksort , au un timp de rulare în cel mai rău caz de O (n ² ), dar un timp de rulare de caz mediu de O (nlog (n)), unde n este lungimea intrarea de sortat.

Criptografie

Pentru majoritatea problemelor, se realizează o analiză complexă a cazului mediu pentru a găsi algoritmi eficienți pentru o problemă care este considerată dificilă în cel mai rău caz. În aplicațiile criptografice, totuși, este adevărat opusul: complexitatea în cel mai rău caz este irelevantă; în schimb, dorim o garanție că complexitatea medie-caz a fiecărui algoritm care „rupe” schema criptografică este ineficientă.

Astfel, toate schemele criptografice sigure se bazează pe existența funcțiilor unidirecționale . Deși existența funcțiilor unidirecționale este încă o problemă deschisă, multe funcții unidirecționale candidate se bazează pe probleme dure, cum ar fi factorizarea numărului întreg sau calcularea jurnalului discret . Rețineți că nu este de dorit ca funcția candidată să fie NP-completă deoarece acest lucru ar garanta doar că probabil nu există un algoritm eficient pentru rezolvarea problemei în cel mai rău caz; ceea ce vrem de fapt este o garanție că niciun algoritm eficient nu poate rezolva problema prin intrări aleatorii (adică cazul mediu). De fapt, atât factorizarea întreagă, cât și problemele de log discrete sunt în NP ∩ coNP și, prin urmare, nu se crede că sunt NP-complete. Faptul că toată criptografia este bazată pe existența problemelor de caz mediu intratabile în NP este una dintre motivațiile principale pentru studierea complexității cazurilor medii.

Alte rezultate

În 1990, Impagliazzo și Levin au arătat că, dacă există un algoritm eficient de caz mediu pentru o problemă distNP completă sub distribuția uniformă, atunci există un algoritm de caz mediu pentru fiecare problemă din NP sub orice distribuție eșantionabilă în timp polinomial. Aplicarea acestei teorii la problemele naturale de distribuție rămâne o întrebare deschisă remarcabilă.

În 1992, Ben-David și colab. a arătat că, dacă toate limbile din distNP au algoritmi de decizie buni în medie, au și algoritmi de căutare buni în medie. Mai mult, acestea arată că această concluzie se menține sub o ipoteză mai slabă: dacă fiecare limbaj din NP este ușor în medie pentru algoritmii de decizie în ceea ce privește distribuția uniformă, atunci este ușor și în medie pentru algoritmii de căutare în ceea ce privește distribuția uniformă. Astfel, funcțiile criptografice unidirecționale pot exista numai dacă există probleme distNP peste distribuția uniformă care sunt dificile în medie pentru algoritmii de decizie.

În 1993, Feigenbaum și Fortnow au arătat că nu este posibil să se demonstreze, sub reduceri aleatorii neadaptative, că existența unui algoritm bun în medie pentru o problemă distNP-completă sub distribuția uniformă implică existența celui mai rău caz algoritmi eficienți pentru toate problemele din NP. În 2003, Bogdanov și Trevisan au generalizat acest rezultat la reduceri arbitrare neadaptative. Aceste rezultate arată că este puțin probabil să se facă vreo asociere între complexitatea medie a cazurilor și cea mai proastă prin reduceri.

Vezi si

• Analiza probabilistică a algoritmilor
• Probleme NP-complete
• Complexitatea celui mai prost caz
• Analiza amortizată
• Cel mai bun, cel mai rău și cel mai mediu caz

Referințe

Lecturi suplimentare

Literatura de complexitate medie a cazurilor include următoarele lucrări:

• Franco, John (1986), „Despre performanța probabilistică a algoritmilor pentru problema de satisfacție”, Information Processing Letters , 23 (2): 103–106, doi : 10.1016 / 0020-0190 (86) 90051-7.
• Levin, Leonid (1986), „Probleme medii complete ale cazului”, SIAM Journal on Computing , 15 (1): 285–286, doi : 10.1137 / 0215020.
• Flajolet, Philippe ; Vitter, JS (august 1987), Analiza cazurilor medii a algoritmilor și structurilor de date , Tech. Raport, Institutul Național de Căutare în Informatică și Automatică, BP 105-78153 Le Chesnay Cedex France.
• Gurevich, Yuri ; Shelah, Saharon (1987), „Timpul de calcul așteptat pentru problema căii hamiltoniene ”, SIAM Journal on Computing , 16 (3): 486-502, CiteSeerX  10.1.1.359.8982 , doi : 10.1137 / 0216034.
• Ben-David, Shai; Chor, Benny; Goldreich, Oded ; Luby, Michael (1989), „Despre teoria complexității medii a cazurilor”, Proc. Cel de-al 21-lea Simpozion anual pe teoria calculelor , Asociația pentru mașini de calcul , pp. 204–216.
• Gurevich, Yuri (1991), „ Completitatea medie a cazurilor”, Journal of Computer and System Sciences , 42 (3): 346-398, doi : 10.1016 / 0022-0000 (91) 90007-R , hdl : 2027.42 / 29307. A se vedea, de asemenea, proiectul din 1989 .
• Selman, B .; Mitchell, D .; Levesque, H. (1992), „Distribuții grele și ușoare ale problemelor SAT”, Proc. A 10-a Conferință Națională despre Inteligența Artificială , pp. 459–465.
• Schuler, Rainer; Yamakami, Tomoyuki (1992), „Complexitate medie structurală a cazurilor”, Proc. Fundamentele tehnologiei software și informaticii teoretice , Note de curs în informatică, 652 , Springer-Verlag, pp. 128-139.
• Reischuk, Rüdiger; Schindelhauer, Christian (1993), „Complexitate medie exactă a cazului”, Proc. Al 10-lea Simpozion anual privind aspectele teoretice ale informaticii , pp. 650-661.
• Venkatesan, R .; Rajagopalan, S. (1992), "Intractabilitatea medie a cazurilor problemelor matricei și diofantine", Proc. Al 24-lea Simpozion Anual de Teorie a Calculelor , Asociația pentru Mașini de Calcul , pp. 632–642.
• Cox, Jim; Ericson, Lars; Mishra, Bud (1995), Complexitatea medie a cazurilor silogistice pe mai multe niveluri (PDF) , Raport tehnic TR1995-711, Departamentul de informatică al Universității din New York.
• Impagliazzo, Russell (17 aprilie 1995), O viziune personală a complexității medii a cazurilor , Universitatea din California, San Diego.
• Paul E. Black, „Θ” , în Dicționar de algoritmi și structuri de date [online] Paul E. Black, ed., Institutul Național de Standarde și Tehnologie al SUA. 17 decembrie 2004. Accesat la 20 februarie 09.
• Christos Papadimitriou (1994). Complexitatea Computațională. Addison-Wesley.