Složenost prosečnog slučaja

U teoriji kompleksnosti, složenost prosečnog slučaja određenog algoritma predstavlja iskorišćenost nekog računarskog resursa (najčešće vremena) u proseku za sve moguće ulaze. Često se suprotstavlja složenosti najgoreg slučaja koja podrazumeva maksimalnu složenost algoritma uzimajući u obzir sve moguće ulaze.

Postoje tri osnovne motivacije za proučavanje složenosti prosečnog slučaja. Prvo, iako neki problemi mogu biti složeni u najgorem slučaju, ulazi koji izazivaju ovakvo ponašanje se možda retko javljaju u praksi, tako da u tom slučaju analiza prosečne složenosti može dati preciznije rezultate prilikom procene složenosti algoritma. Drugo, analiza složenosti prosečnog slučaja obezbeđuje alate i tehnike za generisanje primera problema koji se mogu koristiti u oblastima kao što su kriptografija i derandomizacija (en. derandomization). I treća motivacija, složenost prosečnog slučaja omogućava razlikovanje najefikasnijeg algoritma u praksi među algoritmima sa ekvivalentno zasnovanom složenošću (npr. kviksort).

Analiza složenosti prosečnog slučaja zahteva razumevanje pojma "prosečnog" ulaza algoritma, što dovodi do problema raspodele verovatnoće nad ulazima. Alternativno, može se koristiti randomizovani algoritam. Analiza takvih algoritama dovodi do srodnog pojma očekivane složenosti.

Istorija i pozadina

Efikasnost algoritama u prosečnom slučaju je počela da se izučava pojavom savremenih pojmova efikasnosti izračunavanja koji su razvijeni 1950—ih godina. Veći deo ovog inicijalnog rada je bio fokusiran na probleme za koje su već bili poznati algoritmi sa polinomijalnom vremenskom složenošću u najgorem slučaju. 1973. godine, Donald Knut je objavio 3. tom monografije Umetnost računarskog programiranja (engl. The Art of Computer Programming) koja opširno istražuje efikasnost prosečnog slučaja algoritama za probleme rešive u polinomijalnom vremenu u najgorem slučaju (npr. sortiranje i traženje medijane).

Efikasan algoritam za NP-kompletne probleme je okarakterisan kao algoritam koji se izvršava u polinomijalnom vremenu za sve ulaze; to je ekvivalentno zahtevu za efikasnu složenost u najgorem slučaju. Međutim, algoritam koji je neefikasan za mali broj ulaza i dalje može biti efikasan za većinu ulaza koji se javljaju u praksi. Prema tome, poželjno je proučavati svojstva ovih algoritama gde se prosečna složenost može razlikovati od složenosti najgoreg slučaja i pronaći način za nalaženje veze između njih.

Fundamentalne pojmove složenosti prosečnog slučaja je 1986. godine razvio Leonid Levin kada je objavio jednostrani rad definisanjem složenosti prosečnog slučaja i kompletnosti kroz primer za distNP.

Definicije

Efikasnost složenosti prosečnog slučaja

Prvi zadatak je precizno definisati šta se podrazumeva pod algoritmom čija je složenost "u proseku". Inicijalni pokušaj bi bio da pokušamo da definišemo efikasan algoritam prosečne složenosti kao algoritam koji se izvršava u očekivanom polinomijalnom vremenu za sve moguće ulaze. Ovakva definicija ima razne nedostatke; specijalno, nije robusna promenama u modelu izračunavanja. Na primer, pretpostavimo da se algoritam A izvršava u vremenu t_A(x) za ulaz x i algoritam B se izvršava u vremenu t_A(x)² za ulaz x; tj, B je kvadratno sporiji od A. Intuitivno, bilo koja definicija složenosti prosečnog slučaja bi trebalo da obuhvati ideju da je A efikasan u proseku ako i samo ako je B efikasan u proseku. Pretpostavimo, međutim, da su svi ulazi izvedeni nasumično iz uniformne distribucije niski dužine n, i da se A izvršava u vremenu n² za sve ulaze izuzev za stringove 1ⁿ koji zahtevaju 2ⁿ vremena. Onda se lako može proveriti da je očekivano vreme izvršavanja algoritma A polinomijalno, ali očekivano vreme izvršavanja algoritma B je eksponencijalno. Za kreiranje robusnije definicije složenosti prosečnog slučaja, ima smisla dozvoliti algoritmu A da se izvršava duže od polinomijalnog vremena za neke ulaze, ali da deo ulaza za koje A zahteva sve veće i veće vreme izvršavanja postaje sve manji i manji. Ova intuicija je obuhvaćena narednom formulom za prosečno polinomijalno vreme izvršavanja, koja balansira polinomijalni kompromis između vremena izvršavanja i dela ulaza:

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

za svako n, t, ε > 0 i polinom p, gde t_A(x) označava vreme izvršavanja algoritma A za ulaz x. Alternativno, ovo može biti zapisano kao

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

za neku konstantu C, gde je n = |x|. Drugačije rečeno, algoritam A ima ima dobru složenost prosečnog slučaja ako, nakon pokretanja za t_A(n) koraka, A može da reši sve osim ${\frac {n^{c}}{(t_{A}(n))^{\epsilon }}}$ delova ulaza dužine n, za neke ε, c > 0.

Problem raspodele

Sledeći korak je definisanje prosečnog ulaza za određeni problem. Ovo se postiže udruživanjem ulaza svakog problema sa konkretnom raspodelom verovatnoće. Problem prosečnog slučaja se sastoji od jezika L i pridružene raspodele verovatnoće D koja formira par (L, D). Dve najčešće klase raspodele koje su dozvoljene su:

1. Polinomijalno izračunljive raspodele (P-izračunljive): ovo su raspodele za koje je moguće izračunati kumulativnu gustinu za bilo koji ulaz x. Formalnije, za datu raspodelu verovatnoće μ i nisku x ∈ {0, 1}ⁿ moguće je izračunati sve moguće vrednosti $\mu (x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]$ u polinomijalnom vremenu. Ovo podrazumeva da je Pr[x] takođe izračunljiv u polinomijalnom vremenu.
2. Polinomijalno uzorkovane raspodele (P-uzorkovane): ovo su raspodele iz kojih je moguće izvući nasumične uzorke u polinomijalnom vremenu.

Ove dve formulacije, iako su slične, nisu ekvivalentne. Ako je raspodela P-izračunljiva ona je takođe i P-uzorkovana, ali obrnuto nije tačno ako P ≠ P^#P.

AvgP i distNP

Problem raspodele (L, D) je u klasi složenosti AvgP ako postoji efikasni algoritam prosečne složenosti za L, kao što je definisano gore. Klasa AvgP se u literaturi ponekad naziva distP.

Problem raspodele (L, D) je u klasi složenosti distNP ako je L u NP i ako je D P-izračunljiva. Kada je L u NP i D je P-uzorkovana, (L, D) pripada sampNP.

Zajedno, AvgP i distNP definišu analogije prosečnog slučaja od P i NP.

Redukcije između problema raspodele

Neka su (L,D) i (L',D') dva problema raspodele. Prosečan slučaj (L, D) se redukuje na (L', D') (piše se (L, D) ≤_AvgP (L', D')) ako postoji funkcija f koja za svako n, za ulaz x može biti izračunata u polinomijalnom vremenu od n i

1. (Ispravnost) x ∈ L ako i samo ako f(x) ∈ L'
2. (Dominacija) Postoje polinomi p and m takvi da, ѕa svako n i y, $\sum \limits _{x:f(x)=y}D_{n}(x)\leq p(n)D'_{m(n)}(y)$

Uslov dominacije nameće ideju da ako je problem (L, D) težak u proseku, onda je i (L', D') takođe težak u proseku. Intuitivno, redukcija bi trebalo da obezbedi način rešavanja instance x problema L izračunavanjem f(x) i prosleđivanjem izlaza algoritmu koji rešava L'. Bez ovog uslova, ovo možda ne bi bilo moguće pošto algoritam koji rešava L u polinomijalnom vremenu u proseku može trajati u vremenu koje nije polinomijalno za mali broj ulaza, ali f možda preslikava ove ulaze u mnogo veći skup D', pa se onda algoritam A' više ne izvršava u polinomijalnom vremenu u proseku.

DistNP-kompletni problemi

Analogija prosečne složenosti NP-kompletnosti je distNP-kompletnost. Problem raspodele (L', D') je distNP-kompletan ako je (L', D') u distNP i za svaku (L, D) u distNP, (L, D) je svodljiva na (L', D').

Primer distNP-kompletnog problema je ograničeni Halting problem, BH, definisan kao:

BH = {(M,x,1^t) : M je nedeterministička Tjuringova mašina koja prihvata x u ≤ t koraka.}

U njegovom originalnom radu, Levin prikazuje primer distributivnog popločavanja koji je NP-kompletan. Istraživanja poznatih distNP-kompletnih problema su dostupna na Vebu.

Jedna oblast aktivnog istraživanja uključuje pronalaženje novih distNP-kompletnih problema. Međutim, pronalaženje takvih problema može biti komplikovano zbog rezultata Gureviča koji pokazuju da bilo koji problem raspodele sa plitkom raspodelom ne može biti distNP-kompletan osim ukoliko ne važi EXP = NEXP. (Plitka raspodela μ je raspodela za koju važi da je ε > 0 za svako x, μ(x) ≤ 2^-|x|ε.) Livnovi rezultati pokazuju da svi prirodni NP problemi imaju DistNP-kompletne verzije. Međutim, cilj pronalaženja prirodnih problema raspodele koji su DistNP-kompletni i dalje nije postignut.

Primene

Algoritmi sortiranja

Kao što je već rečeno, mnogo ranih radova se odnosi na složenost prosečnog slučaja za probleme za koje algoritmi sa polinomijalnom složenošću već postoje (npr. sortiranje). Na primer, mnogi algoritmi sortiranja koji koriste slučajnost (npr. kviksort), u najgorem slučaju imaju složenost O(n²), ali u prosečnom slučaju vreme izvršavanja je O(nlog(n)), gde n predstavlja veličinu ulaza koji se sortira.

Kriptografija

Za mnoge probleme, analiza složenosti prosečnog slučaja se vrši kako bi se pronašli efikasni algoritmi za probleme za koje se smatra da su teški u najgorem slučaju. Kod primena u kriptografiji, međutim, važi obrnuto: složenost najgoreg slučaja je irelevantna; umesto toga želimo da garantujemo da je složenost prosečnog slučaja za svaki algoritam koji razbija enkripciju neefikasan.

Prema tome, sve enkripcije se zasnivaju na postojanju takozvanih one-way funkcija (funkcije koje se lako izračunavaju u jednom smeru, ali u suprotnom smeru ne). Iako je postojanje one-way funkcija i dalje otvoren problem, mnogi kandidati one-way funkcija su bazirani na NP-teškim problemima kao što su faktorizacija celih brojeva ili proračunavanje diskretnog logaritma. Potrebno je naglasiti da nije poželjno da funkcija kandidat bude NP-kompletna zato što to garantuje samo da najverovatnije ne postoji efikasan algoritam za rešavanje problema u najgorem slučaju; ono što mi zapravo želimo je da garantujemo da ne postoji efikasan algoritam koji rešava problem za slučajne ulaze. Zapravo, i faktorizacija brojeva i diskretni logaritam su u NP ∩ coNP i zbog toga se ne veruje da su NP-kompletni. Činjenica da je cela kriptografija zasnovana na postojanju složenosti prosečnih slučajeva složenih problema u NP je jedna od glavnih motivacija za izučavanje prosečne složenosti.

Drugi rezultati

1990-ih, Impagliazzo i Levin pokazuju da ako postoji efikasan algoritam u prosečnom slučaju za distNP-kompletan problem prema uniformnoj raspodeli, onda postoji algoritam u prosečnom slučaju za svaki problem u NP prema bilo kojoj polinomijalno uzorkovanoj raspodeli. Primene ove teorije za prirodne raspodele i dalje ostaju kao otvoreno pitanje.

1992., Ben-David et al., pokazuju da ako svi jezici u distNP imaju u proseku dobre algoritme odlučivanja, oni takođe u proseku imaju i dobre algoritme za pretragu. Dodatno, oni pokazuju da ovaj zaključak važi i pod slabijom pretpostavkom: ako je svaki jezik u NP u proseku lak za algoritme odlučivanja u pogledu unoformne raspodele, onda je on takođe lak u proseku i za algoritme za pretragu u pogledu uniformne raspodele. Prema tome, kriptografičke one-way funkcije mogu da postoje samo ako postoje distNP problemi u pogledu uniformne raspodele koji su teški u proseku za algoritme odlučivanja.

1993., Feigenbaum i Fortnow pokazuju da nije moguće dokazati, pod neprilagodljivim slučajnim redukcijama, da postojanje u proseku dobrog algoritma za distNP-kompletan problem prema uniformnoj raspodeli implicira postojanje efikasnog algoritma u najgorem slučaju za sve probleme u NP. 2003., Bogdanov i Trevisan generalizuju ovaj rezultat za proizvoljne neprilagodljive redukcije. Ovi rezultati pokazuju da verovatno nije moguće pronaći vezu između složenosti prosečnog slučaja i složenosti najgoreg slučaja preko redukcija.

Vidi još

• Analiza algoritama
• NP-kompletni problemi

Literatura

• J. Katz; Y. Lindell (2007). Introduction to Modern Cryptography (Chapman and Hall/Crc Cryptography and Network Security Series). Chapman and Hall/CRC.