Hipoteza eksponencijalnog vremena

U teoriji računske složenosti, hipoteza eksponencijalnog vremena predstavlja nedokazanu pretpostavku koja je formulisana od strane Impagliacija i Paturija 1999. godine. Hipoteza tvrdi da 3-SAT, ili bilo koji od nekoliko sličnih NP problema, ne može biti rešen u subeksponencijalnom vremenu u najgorem slučaju. Hipoteza eksponencijalnog vremena, ako je istinita, podrazumevala bi da je P ≠ NP. Mogla bi da se iskoristi da se pokaže da su mnogi računarski problemi jednaki u kompleksnosti, u smislu da ako jedan od njih ima algoritam u subeksponencijalnom vremenu, svi ga imaju.

Definicija

k-SAT je problem testiranja da li Bulova formula, u konjuktivnoj normalnoj formi sa najviše k promenljivih, može biti istinita po nekoj dodeli bulovih vrednosti svojim promenljivama. Za svaki ceo broj k ≥ 2, definisati realni broj s_k tako da bude infimum realnih brojeva δ za koje postoji algoritam rešavanja k-SAT u vremenu O(2^δn), gde je n broj promenljivih u datoj k-SAT instanci. Tada je s₂ = 0, jer 2-SAT može biti rešen u polinomijalnom vremenu. Hipoteza eksponencijalnog vremena je pretpostavka da za svako k > 2, s_k > 0. Jasno, s₃ ≤ s₄ ≤ ..., tako da je ekvivalentno pretpostaviti da je s₃ > 0. Pozitivnost preostalih brojeva s_k sledi automatski od ove pretpostavke.

Neki izvori definišu hipotezu eksponencijalnog vremena kao malo slabiju izjavu da 3-SAT ne može biti rešen u 2^o(n) vremenu. Ako bi postojao algoritam koji rešava 3-SAT problem u 2^o(n) vremenu, onda bi očito s₃ bilo jednako nuli. Međutim, to je u skladu sa dosadašnjim znanjem da bi mogla postojati sekvenca 3-SAT algoritama, svaka sa vremenom O(2^δ_in) za sekvencu brojeva δ_i koja teži nuli, ali gde opisi ovih algoritama rastu tako brzo da najprikladniji algoritam ne bi mogao automatski da se odabere i pokrene.

S obzirom da brojevi s₃, s₄, ... formiraju monotonu sekvencu koja je ograničena brojem 1 iznad, moraju konvergirati do granice s_∞. Hipoteza jakog eksponencijalnog vremena (SETH) je pretpostavka da ograničavajuća vrednost s_∞ sekvence brojeva s_k je jednaka nuli. Druga varijanta je neuniformna hipoteza eksponencijalnog vremena, koja pretpostavlja da ne postoji familija algoritama koja može rešiti 3-SAT u vremenu 2^o(n).

Implikacije zadovoljenja

Nije moguće da s_k bude jednak s_∞ beskonačno za bilo koje konačno k. Kako su Impagliacio, Paturi i Zejn pokazali 2001. godine, postoji konstanta α takva da je s_k ≤ s_∞(1 − α/k). Samim tim, ako je hipoteza eksponencijalnog vremena tačna, mora postojati beskonačno mnogo vrednosti k za koje se s_k razlikuje od s_k + 1.

Važni pojam u ovoj oblasti je lema proređivanja Impagliacija, Paturija i Zejna (2001), koja pokazuje da za bio koje ε > 0, bilo koja k-CNF formula može biti zamenjena O(2^εn) jednostavnijom k-CNF formulom u kojoj bi se svaka promenljiva pojavljivala samo konačan broj puta, i samim tim je broj članova konačan. Lema proređivanja je dokazana ponavljajućim pronalaženjima velikih skupova tačaka koje imaju neprazni zajednički presek u datoj formuli, i zamenom formule dvema jednostavnijim formulama, od kojih jedna ima ove tačke zamenjene zajedničkim presekom, a druga ima presek uklonjen iz svake tačke. Primenom leme proređivanja i zatim korišćenjem novih promenljivih kako bismo podelili tačke, jedna onda može da dobije skup O(2^εn) 3-CNF formula, svaka sa linearnim brojem promenljivih, takva da je originalna k-CNF formula zadovoljavajuća ako i samo ako je bar jedna od ove tri 3-CNF formule zadovoljavajuća. Dakle, ako bi 3-SAT mogao biti rešen u subeksponencijalnom vremenu, mogla bi se iskoristiti ova redukcija kako bi se rešio k-SAT, takođe u subeksponencijalnom vremenu. Ekvivalentno, ako je s_k > 0 za bilo koje k > 3, onda je i s₃ > 0, i hipoteza eksponencijalnog vremena bi bila istinita.

Granična vrednost s_∞ sekvence brojeva s_k je najviše jednaka sCNF, gde je sCNF infimum brojeva δ takvih da zadovoljivost vezivnih formula normalne forme bez limita dužine može biti rešeno u O(2^δn). Dakle, ako je hipoteza jakog eksponencijalnog vremena istinita, onda ne bi bilo algoritma za generalnu CNF zadovoljivost koja je značajno brža u odnosu na testiranje svih mogućih zadataka. Međutim, ako hipoteza brzog eksponencijalnog vremena nije tačna, i dalje bi bilo moguće za s_CNF da bude jednak jedinici.

Implikacije za druge probleme pretrage

Hipoteza eksponencijalnog vremena podrazumeva da mnogi drugi problemi u klasi kompleksnosti SNP nemaju algoritme čije je vreme izvršenja brže od cⁿ za neku konstantu  c. Ovi problemi uključuju bojenje grafova, pronalaženje Hamiltonovih ciklusa, maksimalnih nezavisnih skupova, itd. Nasuprot tome, ako ijedan od ovih problema ima subeksponencijalni algoritam, onda hipoteza eksponencijalnog vremena nije tačna. Ako se klike ili nezavisni skupovi logaritamskih veličina mogu naći u polinomijalnom vremenu, hipoteza eksponencijalnog vremena nije tačna. Samim tim, iako pronalaženje klika ili nezavisnih skupova malih veličina najverovatnije nije NP kompletno, hipoteza eksponencijalnog vremena implicira da su ovi problemi nepolinomijalni. Uopšteno govoreći, hipoteza eksponencijalnog vremena implicira da nije moguće naći klike ili nezavisne setove veličine k u vremenu n^o(k). Hipoteza eksponencijalnog vremena takođe implicira da nije moguće rešiti k-SUM problem, u vremenu 'n^o(k), kao i da nije moguće naći skupove sa k dominirajućih čvorova brže nego u nk − o(1) vremenu.

Hipoteza jakog eksponencijalnog vremena dovodi do uskih granica na parametrizovanoj složenosti nekoliko problema grafova. Konkretno, ako je hipoteza jakog eksponencijalnog vremena tačna, onda bi granica optimalnog vremena za pronalaženje nezavisnih skupova na grafu širine w bila (2 − o(1))^wn^O(1), optimalno vreme za dominirajući problem skupova (3 − o(1))^wn^O(1) a optimalno vreme za k bojenje je (k − o(1))^wn^O(1). Ekvivalentno, bilo kakvo poboljšanje u ovim vremenima izvršenja bi opovrgnula hipotezu jakog eksponencijalnog vremena.

Implikacije u strukturalnoj kompleksnosti

Ako je hipoteza eksponencijalnog vremena tačna, onda 3-SAT ne bi imao algoritam u polinomijalnom vremenu, što bi značilo da je P različito od NP. U ovom slučaju, 3-SAT ne bi čak ni imao algoritam u kvazi-polinomijalnom vremenu, pa NP ne bi bio ni podskup od QP. Ipak, ako hipoteza eksponencijalnog vremena nije tačna, ne bi bilo implikacija za P nasuprot NP problem. Postoje NP kompletni problemi za koje poznato najbolje vreme ima formu O(2^nc) za c < 1, i ako bi najbolje moguće vreme izvršavanja za 3-SAT bilo u ovom obliku, onda bi P bilo različito od NP, jer je 2-SAT Np kompletno i ova granica nije polinomijalna, ali bi hipoteza eksponencijalnog vremena bila netačna.

U parametrizovanoj teoriji kompleksnosti, jer hipoteza eksponencijalnog vremena implicira da ne postoji algoritam fiksnog parametra za maksimum kliku, takođe implicira da je W[1] ≠ FPT. Ovo je bitan otvoreni problem bilo da se ova implikacija može obrnuti: da li W[1] ≠ FPT implicira hipotezu eksponencijalnog vremena? Postoji hijerarhija parametrizovanih klasa kompleksnosti nazvana M hijerarija koja se meša u W hijerarhiju u smislu da, za svako i, M[i] ⊆ W[i] ⊆ M[i + 1]. Hipoteza eksponencijalnog vremena je ekvivalentna tvrdnji da M[1] ≠ FPT, i pitanje da li je M[i] = W[i] za i > 1 je takođe otvoreno. Takođe je moguće dokazati implikacije u drugom smeru, od neuspeha varijacija hipoteze jakog eksponencijalnog vremena do razdvajanja klasa kompleksnosti. Kako je Vilijams pokazao 2010. godine, ako postoji algoritam A koji rešava Bulov krug zadovoljivosti u vremenu 2ⁿ/ƒ(n) za neke superpolinomijalne rastuće funkcije  ƒ, onda NEXPTIME nije podskup P/poly.

Literatura

1. "Exact algorithms for NP-hard problems" Архивирано на сајту Wayback Machine (30. септембар 2020)
2. "Improving exhaustive search implies superpolynomial lower bounds"
3. . doi:10.1007/978-3-642-17517-6_3.  "Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament"
4. "Which problems have strongly exponential complexity?"