Conjectura timpului exponențial

Conjectura timpului exponențial este o presupunere nedovedită despre complexitatea computațională care a fost formulată de Impagliazzo și Paturi [1] . Conjectura afirmă că 3-SAT (sau oricare dintre problemele NP-complete aferente ) nu poate fi rezolvată în timp sub-exponențial în cel mai rău caz [2] . Valabilitatea conjecturii de timp exponențial, dacă este adevărată, ar implica că P ≠ NP , dar conjectura este o afirmație mai puternică. Din enunțul ipotezei, se poate arăta că multe probleme de calcul sunt echivalente ca complexitate în sensul că dacă una dintre ele are un algoritm de timp exponențial, atunci toate au algoritmi de aceeași complexitate.

Definiție

Sarcina k -SAT este sarcina de a verifica dacă o expresie booleană în formă normală conjunctivă care are mai mult de k variabile pe expresie (conjunctivă) poate fi făcută adevărată prin atribuirea valorii valorilor booleene variabilelor expresiei. Pentru orice număr întreg , definim un număr real ca fiind infimul numerelor reale , pentru care există un algoritm pentru rezolvarea problemei k -SAT în timp , unde n este numărul de variabile din această problemă k -SAT. Atunci , deoarece problema 2-SAT poate fi rezolvată în timp polinomial . Ipoteza timpului exponenţial este ipoteza că pentru orice . Este clar că , deci conjectura este echivalentă cu ipoteza că , pozitivitatea numerelor rămase decurge automat din ipoteză. $k\geqslant 2$ $s_{k)$ $\delta$ $O(2^{\delta n})$ $s_{2}=0$ $k>2,s_{k}>0$ $s_{3}\leqslant s_{4}\leqslant \ldots$ $s_{3}>0$ $s_{k)$

Unele surse definesc conjectura timpului exponențial ca o afirmație puțin mai slabă că 3-SAT nu poate fi rezolvată în timp . Dacă există un algoritm pentru rezolvarea problemei 3-SAT în timp , atunci este clar că va fi egal cu zero. Cu toate acestea, acest lucru este în concordanță cu cunoștințele actuale că poate exista o secvență de algoritmi 3-SAT, fiecare rulând în timp pentru numere care tind spre zero, dar descrierea acestor algoritmi crește rapid, astfel încât un singur algoritm nu poate selecta și executa automat. cel mai potrivit algoritm. [3] . $2^{o(n)}$ $2^{o(n)}$ $s_{3)$ $O(2^{\delta _{i}n})$ $\delta _{i}$

Deoarece numerele formează o succesiune monotonă , care este mărginită de sus de unul, ele trebuie să convergă către limită . Conjectura de timp exponențială puternică (SETH) este ipoteza că valoarea limită s ∞ a unei secvențe de numere s k este egală cu unu [4] . $s_{3},s_{4},\ldots$ ${\displaystyle s_{\infty ))$

O altă versiune a conjecturei este conjectura de timp exponențială eterogenă , care întărește a doua parte a ETH, care postulează că nu există o familie de algoritmi (câte unul pentru fiecare lungime de intrare în spiritul hint ) care să poată rezolva problema 3- Problemă SAT în timp 2 o( n ) .

Corolarul satisfacției

Nu poate fi egal pentru orice k finit - așa cum au arătat Impagliazzo, Paturi și Zane [5] , există o constantă astfel încât . Prin urmare, dacă ipoteza timpului exponențial este adevărată, trebuie să existe infinite de valori ale lui k pentru care s k diferă de . $s_{k)$ ${\displaystyle s_{\infty ))$ $\alfa$ $s_{k}\leqslant s_{\infty}(1-\alpha /k)$ $s_{k+1}$

Un instrument important în acest domeniu este lema raritate a lui Impagliazzo, Paturi și Zane [5] , care arată că pentru orice formulă k -CNF poate fi înlocuită cu formule k -CNF mai simple în care fiecare variabilă apare doar un număr constant de ori, și astfel numărul de propoziții este liniar. Lema de dispersie este dovedită prin găsirea succesivă a unor seturi mari de expresii care au o intersecție comună nevidă într-o formulă dată și înlocuirea formulei cu două formule mai simple, în una dintre care fiecare astfel de expresie este înlocuită cu intersecția lor comună, iar în cealaltă intersecție este eliminată din fiecare expresie. Aplicând lema rară și folosind noi variabile pentru a împărți expresii, se poate obține un set de formule 3-CNF, fiecare cu un număr liniar de variabile, astfel încât formula originală k -CNF să fie satisfăcătoare dacă și numai dacă cel puțin una dintre aceste formule 3-CNF sunt fezabile. Astfel, dacă 3-SAT ar putea fi rezolvată în timp sub-exponenţial, se poate folosi această reducere pentru a rezolva problema k - SAT în timp sub-exponenţial. În mod echivalent, dacă pentru orice k > 3, atunci este adevărată și conjectura de timp exponențial [2] [5] . $\epsilon > 0$ $O(2^{{\epsilon }n})$ $O(2^{\epsilon }n)$ $s_{k}>0$ $s_{3}>0$

Valoarea limită a succesiunii de numere s k nu depăşeşte s CNF , unde s CNF este infimumul numerelor astfel încât satisfacabilitatea formulelor în formă normală conjunctivă fără a limita lungimea expresiei poate fi rezolvată în timp . Astfel, dacă conjectura de timp exponențială puternică este adevărată, atunci nu există un algoritm pentru problema generală de satisfacție CNF care să fie substanțial mai rapid decât testarea tuturor propozițiilor posibile pentru adevăr . Totuși, dacă conjectura puternică despre timpul exponențial nu este adevărată, rămâne posibil ca s CNF să fie egal cu unu [6] . ${\displaystyle s_{\infty ))$ $\delta$ $O(2:{{\delta }n})$

Consecințe pentru problemele de căutare

Conjectura timpului exponențial implică faptul că multe alte probleme din clasa de complexitate SNP nu au algoritmi al căror timp de rulare este mai mic decât c n pentru o constantă c . Aceste probleme includ graficul k -colorabilitatea , găsirea ciclurilor hamiltoniene , cele mai mari clicuri , cele mai mari mulțimi independente și acoperiri de vârfuri pe grafice cu n vârfuri. În schimb, dacă oricare dintre aceste probleme are un algoritm subexponențial, atunci va fi posibil să arătăm că conjectura timpului exponențial este falsă [2] [5] .

Dacă clicurile sau seturile independente de mărime logaritmică ar putea fi găsite în timp polinomial, conjectura timpului exponențial ar fi greșită. Astfel, chiar dacă găsirea unor clicuri sau mulțimi independente de dimensiuni atât de mici este puțin probabil să fie NP-completă, conjectura în timp exponențial implică faptul că aceste probleme nu sunt polinomiale [2] [7] . Mai general, conjectura timpului exponențial implică faptul că este imposibil să găsești clicuri sau mulțimi independente de mărime k în timp [8] . Ipoteza timpului exponențial implică, de asemenea, că este imposibil să se rezolve problema k -SUM (având în vedere n numere reale, trebuie să găsiți k dintre ele, dând suma zero) în timp . Conjectura exponențială puternică a timpului implică faptul că este imposibil să se găsească mulțimi dominante formate din k vârfuri în mai puțin de timp [6] . $n^{o(k)}$ $n^{o(k)}$ $n^{ko(1)}$

De asemenea, din ipoteza timpului exponențial rezultă că problema ponderată a găsirii unui set de arce de tăiere a ciclului în turnee (FAST) nu are un algoritm parametric cu timp de rulare , nici măcar nu are un algoritm parametric cu timp de rulare [9] . $O^{*}(2^{o({\sqrt {OPT)})})$ $O^{*}(2^{O({\sqrt {OPT)})})$

Conjectura de timp exponențială puternică duce la limite clare ale complexității parametrizate a unor probleme pe grafice cu lățime de arbore mărginită . În special, dacă conjectura de timp exponențială puternică este adevărată, atunci limita optimă de timp pentru găsirea mulțimilor independente pe grafice cu lățimea arborelui estew [10] . În mod echivalent, orice îmbunătățire a acestor timpi de rulare ar invalida conjectura puternică a timpului exponențial [11] . Din ipoteza timpului exponențial rezultă, de asemenea, că orice algoritm fix-parametric decidabil pentru acoperirea muchiilor unui graf cu clicuri trebuie să aibă o dublă dependență exponențială de parametrul [12] . $(2o(1))^{w}n^{O(1)}$ $(3-o(1))^{w}n^{O(1))$ $(2-o(1))^{w}n^{O(1))$ $(ko(1))^{w}n^{O(1)}$

Implicații în teoria complexității comunicării

În problema disjuncției tripartite a mulțimilor în complexitatea comunicării, sunt date trei subseturi de numere întregi dintr-un interval [1, m ] și sunt dați trei participanți comunicanți, fiecare dintre care cunoaște două din cele trei submulțimi. Scopul participanților este de a transfera cât mai puține biți de informații unul către celălalt pe un canal de comunicare comun, dar astfel încât unul dintre participanți să poată determina dacă intersecția celor trei seturi este goală sau nu. Un protocol banal de m -biți ar fi trimiterea unuia dintre participanții vectorului de biți care descrie intersecția a două mulțimi cunoscute de el, după care fiecare dintre cei doi participanți rămași poate determina golul intersecției. Cu toate acestea, dacă există un protocol care rezolvă problema în o( m ) sărituri și calcule, acesta poate fi convertit într-un algoritm k -SAT în timp O(1,74 n ) pentru orice constantă fixă k , ceea ce încalcă ipoteza timpului exponențial puternic. . Prin urmare, din conjectura puternică despre timpul exponențial rezultă că fie protocolul banal pentru problema disjunctivității tripartite a mulțimilor este optim, fie orice protocol mai bun necesită un număr exponențial de calcule [6] . $2^{o(m)}$

Consecințe în teoria complexității structurale

Dacă ipoteza timpului exponențial este corectă, atunci 3-SAT nu ar trebui să aibă un algoritm de timp polinomial și astfel ar rezulta că P ≠ NP . Mai puternic, în acest caz, problema 3-SAT nu ar avea nici măcar un algoritm de timp cvasi-polinomial , deci NP nu ar putea fi un subset al clasei QP. Totuși, dacă conjectura exponențială a timpului nu este adevărată, nu ar rezulta că clasele P și NP sunt egale. Există probleme NP-complete pentru care cel mai cunoscut timp de rezolvare este de forma pentru , iar dacă cel mai bun timp de rulare posibil pentru 3-SAT a fost de această formă, atunci P nu ar fi egal cu NP (deoarece 3-SAT este o problemă NP-completă și de data aceasta nu este polinom), dar conjectura exponențială a timpului ar fi greșită. $O(2^{n^{c)))$ $c<1$

În teoria complexității parametrice, deoarece ipoteza timpului exponențial implică că nu există un algoritm fixat-parametric determinabil pentru găsirea celei mai mari clicuri, implică și că W[1] ≠ FPT [8] . Este o problemă deschisă importantă în acest domeniu, se poate inversa acest corolar - urmează conjectura timpului exponențial? Există o ierarhie a claselor de complexitate parametrică numită ierarhia M, care este intercalată cu ierarhia W în sensul că pentru toate i , . De exemplu, problema găsirii unei acoperiri de vârfuri de o dimensiune într-un grafic cu n vârfuri este completă pentru M[1]. Conjectura despre timpul exponenţial este echivalentă cu afirmaţia că , iar problema egalităţii pentru i > 1 rămâne de asemenea deschisă [3] . $W[1]\neq FPT$ $M[i]\subseteq W[i]\subseteq M[i+1]$ $k\log(n)$ $M[1]\neq FPT$ $M[i]=W[i]$

De asemenea, se poate arăta derivarea în cealaltă direcție, de la eșecul conjecturii puternice despre timpul exponențial la separarea claselor de complexitate. După cum a arătat Williams [13] , dacă există un algoritm A care rezolvă problema de satisfacție a timpului boolean pentru o funcție cu creștere superpolinomială , atunci NEXPTIME nu este o submulțime a lui P/poli . Williams a arătat că dacă există algoritmul A și există și o familie de scheme care simulează NEXPTIME în P/poly, atunci algoritmul A ar putea fi combinat cu o schemă pentru a modela sarcinile NEXPTIME în mod nedeterminist în mai puțin timp, ceea ce contrazice Teorema ierarhiei timpului . Astfel, existența algoritmului A dovedește imposibilitatea existenței unei familii de circuite și separarea acestor două clase de complexitate. $2^{n}/f(n)$ $f$

Note

↑ Impagliazzo, Paturi, 1999 .
↑ 1 2 3 4 Woenger, 2003 .
↑ 1 2 Flum, Grohe, 2006 .
↑ Dantsin, Wolpert, 2010 .
↑ 1 2 3 4 Impagliazzo, Paturi, Zane, 2001 .
↑ 1 2 3 Pătraşcu, Williams, 2010 .
↑ Feige, Kilian, 1997 .
↑ 1 2 Chen, Huang, Kanj, Xia, 2006 .
↑ Karpinski, Warren, 2010 .
↑ Cygan, Fomin, Kowalik, Lokshtanov et al., 2015 .
↑ Lokshtanov, Marx, Saurabh, 2011 .
↑ Cygan, Pilipczuk, Pilipczuk, 2013 .
↑ Williams, 2010 .

Literatură

Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia. Limite inferioare de calcul puternice prin complexitatea parametrizată // Journal of Computer and System Sciences. - 2006. - T. 72 , nr. 8 . - S. 1346-1367 . - doi : 10.1016/j.jcss.2006.04.007 .
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh. Algoritmi parametrizați. - Springer, 2015. - P. 555. - ISBN 978-3-319-21274-6 .
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk. Algoritmii cunoscuți pentru EDGE CLIQUE COVER sunt probabil optimi // Proc. Al 24-lea Simpozion ACM-SIAM despre algoritmi discreti (SODA 2013) . - 2013. Arhivat la 16 aprilie 2013.
Evgeny Dantsin, Alexander Wolpert. Teoria și aplicațiile testării de satisfacție–SAT 2010. Springer-Verlag, 2010. Vol. 6175 . - S. 313-325 . - doi : 10.1007/978-3-642-14186-7_27 .
Uriel Feige , Joe Kilian. Pe nondeterminism limitat versus polinomial // Informatică teoretică. - 1997. - Vol. 1 . - P. 1-20 .
Jörg Flum, Martin Grohe. 16. Tractabilitate subexponențială cu parametri fixe // Teoria complexității parametrizate . - Springer-Verlag, 2006. - S. 417 -451. - (Texte EATCS în Informatică Teoretică). — ISBN 978-3-540-29952-3 .
Russell Impagliazzo, Ramamohan Paturi. Complexitatea k-SAT // Proc. a 14-a Conf. IEEE. pe complexitatea computațională . - 1999. - S. 237-240. - doi : 10.1109/CCC.1999.766282 .
Russell Impagliazzo, Ramamohan Paturi, Francis Zane. Care probleme au o complexitate puternic exponențială? // Journal of Computer and System Sciences. - 2001. - T. 63 , nr. 4 . - S. 512-530 . - doi : 10.1006/jcss.2001.1774 .
Marek Karpinski, Schudy Warren. Algoritmi mai rapidi pentru turneul Feedback Arc Set, Kemeny Rank Aggregation and Betweenness Tournament // Proc. ISAAC 2010, Partea I. - 2010. - P. 3-14 . - doi : 10.1007/978-3-642-17517-6_3 .
Daniel Lokshtanov, Daniel Marx, Saket Saurabh. Algoritmii cunoscuți pe grafice cu lățimea arborelui mărginit sunt probabil optimi // Proc. Al 22-lea Simpozion ACM/SIAM despre algoritmi discreti (SODA 2011) . - 2011. - S. 777-789. Arhivat pe 18 octombrie 2012 la Wayback Machine
Mihai Patraşcu, Ryan Williams. Despre posibilitatea unor algoritmi SAT mai rapizi // Proc. Al 21-lea Simpozion ACM/SIAM despre algoritmi discreti (SODA 2010) . - 2010. - S. 1065-1075.
Ryan Williams. Îmbunătățirea căutării exhaustive implică limite inferioare superpolinomiale // Proc. Cel de-al 42-lea Simpozion ACM despre Teoria Calculului (STOC 2010). - New York, NY, SUA: ACM, 2010. - S. 231-240. - doi : 10.1145/1806689.1806723 .
Gerhard J. Woeginger. Algoritmi exacti pentru probleme NP-hard: un sondaj // Optimizare combinatorie — Eureka, You Shrink! . - Springer-Verlag, 2003. - T. 2570. - S. 185-207. - doi : 10.1007/3-540-36478-1_17 .