Exponenciális idősejtés

Az exponenciális idősejtés egy nem bizonyított feltételezés a számítási bonyolultságról , amelyet Impagliazzo és Paturi [1] fogalmazott meg . A sejtés azt állítja, hogy a 3-SAT (vagy bármely kapcsolódó NP-teljes probléma) a legrosszabb esetben nem oldható meg exponenciális idő alatt [2] . Az exponenciális idő hipotézis érvényességéből, ha igaz, az következne, hogy P ≠ NP , de a sejtés erősebb állítás. A hipotézis megállapításából kimutatható, hogy sok számítási probléma komplexitása ekvivalens abban az értelemben, hogy ha az egyiknek van exponenciális idő algoritmusa, akkor mindegyiknek azonos bonyolultságú algoritmusa van.

Definíció

A k -SAT feladat annak ellenőrzése, hogy egy konjunktív normál formájú logikai kifejezés , amely (konjunktív) kifejezésenként több mint k változót tartalmaz, igazzá tehető-e, ha logikai értékeket rendelünk a kifejezés változóihoz. Bármely egész szám esetén a valós számot a valós számok infimumaként definiáljuk , amelyre létezik egy algoritmus a k -SAT probléma időbeni megoldására , ahol n a változók száma ebben a k -SAT feladatban. Ekkor , mivel a 2-SAT feladat polinomiális időben is megoldható . Az exponenciális idő hipotézis az a feltételezés , hogy bármely . Nyilvánvaló, hogy , tehát a sejtés ekvivalens azzal a feltételezéssel, hogy a fennmaradó számok pozitivitása automatikusan következik a feltételezésből. $k\geqslant 2$ ${\displaystyle 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$ ${\displaystyle s_{k))$

Egyes források az exponenciális idősejtést valamivel gyengébb állításként határozzák meg, amely szerint a 3-SAT nem oldható meg időben . Ha van egy algoritmus a 3-SAT probléma időbeni megoldására , akkor egyértelmű, hogy ez egyenlő lesz nullával. Ez azonban összhangban van a jelenlegi ismeretekkel, miszerint létezhetnek 3-SAT algoritmusok sorozata, amelyek mindegyike időben fut a nullára hajlamos számokra , de ezeknek az algoritmusoknak a leírása olyan gyorsan növekszik, hogy egyetlen algoritmus nem képes automatikusan kiválasztani és végrehajtani. a legmegfelelőbb algoritmus [3] . $2^{o(n)}$ $2^{o(n)}$ ${\displaystyle s_{3))$ $O(2^{\delta _{i}n})$ $\delta _{i}$

Mivel a számok monoton sorozatot alkotnak , amelyet felülről eggyel határol, a határértékhez kell konvergálniuk . Az erős exponenciális idősejtés (SETH) az a feltevés, hogy egy s k számsorozat s ∞ határértéke eggyel egyenlő [4] . $s_{3},s_{4},\ldots$ ${\displaystyle s_{\infty ))$

A sejtés másik változata a heterogén exponenciális idősejtés , amely megerősíti az ETH második részét, amely azt feltételezi, hogy nincs olyan algoritmuscsalád (minden bejegyzés hosszához egy az hint szellemében ), amely meg tudná oldani a 3- SAT probléma 2 o( n ) időben .

Kielégíthetőség következménye

Nem lehet egyenlő egyetlen véges k -re sem – amint Impagliazzo, Paturi és Zane [5] megmutatta , létezik olyan állandó , hogy . Ezért, ha az exponenciális idő hipotézise igaz, akkor végtelen sok olyan k értéknek kell lennie , amelyre s k eltér a -tól . ${\displaystyle s_{k))$ ${\displaystyle s_{\infty ))$ $\alpha$ $s_{k}\leqslant s_{\infty }(1-\alpha /k)$ $s_{k+1}$

Ezen a területen fontos eszköz Impagliazzo, Paturi és Zane [5] ritkaságlemmája , amely azt mutatja, hogy bármely k -CNF képletre lecserélhető egyszerűbb k -CNF képlet, amelyben minden változó csak állandó számú alkalommal, és így a mondatok száma lineáris. A ritkaság lemmát úgy bizonyítjuk, hogy egymás után megkeresünk olyan kifejezések nagy halmazait, amelyeknek egy adott képletben nem üres közös metszéspontja van, és a képletet lecseréljük két egyszerűbb képlettel, amelyek közül az egyikben mindegyik kifejezést a közös metszéspontjuk helyettesíti. a másik metszéspontot eltávolítjuk az egyes kifejezésekből. A ritka lemma alkalmazásával és új változók használatával a kifejezések felosztására 3-CNF képletből álló halmazt kaphatunk, amelyek mindegyike lineáris számú változóval rendelkezik, így az eredeti k -CNF formula akkor és csak akkor teljesíthető, ha legalább az egyik ezek a 3-CNF képletek megvalósíthatók. Így, ha a 3-SAT megoldható szubexponenciális időben, akkor ezzel a redukcióval megoldható a k - SAT probléma szubexponenciális időben. Ezzel egyenértékűen, ha bármely k > 3-ra, akkor az exponenciális idősejtés is igaz [2] [5] . $\epsilon > 0$ $O(2^{{\epsilon }n})$ $O(2^{\epsilon }n)$ $s_{k}>0$ $s_{3}>0$

Az s k számsor határértéke nem haladja meg az s CNF - t , ahol s CNF a számok infimuma , így a képletek konjunktív normál alakban való kielégíthetősége a kifejezés hosszának korlátozása nélkül időben megoldható . Így, ha az erős exponenciális idősejtés igaz, akkor nincs olyan algoritmus az általános CNF kielégítési problémára, amely lényegesen gyorsabb lenne, mint az összes lehetséges igazságtétel tesztelése . Ha azonban az exponenciális időre vonatkozó erős sejtés nem igaz, lehetséges, hogy s CNF egyenlő eggyel [6] . ${\displaystyle s_{\infty ))$ $\delta$ $O(2:{{\delta }n})$

A keresési problémák következményei

Az exponenciális idősejtés azt sugallja, hogy az SNP komplexitási osztály sok más problémája nem rendelkezik olyan algoritmusokkal, amelyek futási ideje kisebb, mint c n valamilyen c állandó esetén . Ezek a problémák közé tartozik a gráf k színezhetősége , a Hamilton-ciklusok , a legnagyobb klikkek , a legnagyobb független halmazok és a csúcslefedések keresése n csúcsú gráfokon . Ezzel szemben, ha ezen problémák bármelyikének van szubexponenciális algoritmusa, akkor meg lehet majd mutatni, hogy az exponenciális idősejtés hamis [2] [5] .

Ha logaritmikus méretű klikkeket vagy független halmazokat találnánk a polinomiális időben, akkor az exponenciális idő sejtése téves lenne. Így még ha nem is valószínű, hogy ilyen kis méretű klikkek vagy független halmazok megtalálása NP-teljes, az exponenciális idősejtés azt sugallja, hogy ezek a problémák nem polinomiálisak [2] [7] . Általánosabban fogalmazva, az exponenciális idősejtés azt jelenti, hogy lehetetlen időben k méretű klikkeket vagy független halmazokat találni [8] . Az exponenciális idő hipotézise azt is jelenti, hogy a k -SUM feladatot ( n valós szám esetén k -t kell megtalálni , így az összeg nulla) lehetetlen időben megoldani . Az erős exponenciális idősejtés azt sugallja, hogy lehetetlen k csúcsból álló domináns halmazokat találni rövidebb idő alatt [6] . $n^{o(k)}$ $n^{o(k)}$ $n^{ko(1)}$

Az exponenciális időhipotézisből az is következik, hogy a versenyeken belüli ciklus-vágó ívhalmaz (FAST) súlyozott problémája nem rendelkezik futásidejű paraméteres algoritmussal, sőt futásidejű paraméteres algoritmusa sem [9] . $O^{*}(2^{o({\sqrt {OPT)))})$ $O^{*}(2^{O({\sqrt {OPT)))})$

Az erős exponenciális idősejtés éles határokhoz vezet néhány probléma paraméterezett összetettségében korlátos faszélességű gráfokon . Különösen, ha az erős exponenciális idősejtés igaz, akkor a w faszélességű agráfokon független halmazok megtalálásának optimális időkorlátja egyenlő [10] . Ezzel egyenértékűen ezen futási idők bármilyen javulása érvénytelenítené az erős exponenciális idősejtést [11] . Az exponenciális idő hipotézisből az is következik, hogy bármely fix-parametrikusan eldönthető algoritmusnak, amely a gráf éleit klikkekkel fedi le , kétszeres exponenciális függéssel kell rendelkeznie a [12] paramétertől . $(2o(1))^{w}n^{O(1)}$ ${\displaystyle (3-o(1))^{w}n^{O(1)))$ ${\displaystyle (2-o(1))^{w}n^{O(1)))$ $(ko(1))^{w}n^{O(1)}$

Következtetések a kommunikációs komplexitás elméletében

A kommunikációs komplexitású halmazok tripartit diszjunktságának problémájában valamilyen [1, m ] intervallum egész számainak három részhalmazát adjuk meg, és három kommunikáló résztvevőt adunk meg, amelyek mindegyike ismer a három részhalmazból kettőt. A résztvevők célja, hogy egy közös kommunikációs csatornán minél kevesebb bitnyi információt továbbítsanak egymásnak, de úgy, hogy az egyik résztvevő meg tudja állapítani, hogy a három halmaz metszéspontja üres-e vagy sem. Egy triviális m bites protokoll az lenne, ha az általa ismert két halmaz metszéspontját leíró bitvektor egyik résztvevőjét elküldené , ami után a maradék két résztvevő mindegyike meghatározhatja a metszéspont ürességét. Ha azonban létezik olyan protokoll, amely o( m ) ugrásban és számításokban oldja meg a problémát, akkor az O(1,74 n ) idő alatt k -SAT algoritmussá konvertálható bármely rögzített k állandóra , ami sérti az erős exponenciális idő hipotézist. . Ezért az exponenciális időre vonatkozó erős sejtésből az következik, hogy vagy a halmazok tripartit diszjunktivitásának problémájának triviális protokollja az optimális, vagy bármely jobb protokoll exponenciális számú számítást igényel [6] . $2^{o(m)}$

Következmények a szerkezeti komplexitás elméletében

Ha az exponenciális idő hipotézis helyes, akkor a 3-SAT nem rendelkezhet polinomiális idő algoritmussal, és ebből az következik, hogy P ≠ NP . Még erősebben, ebben az esetben a 3-SAT problémának nem is lenne kvázipolinomiális időalgoritmusa , így NP nem lehet a QP osztály részhalmaza. Ha azonban az exponenciális idősejtés nem igaz, abból nem következik, hogy a P és az NP osztályok egyenlőek. Vannak olyan NP-teljes feladatok, amelyekre a legismertebb megoldási idő a következő alakú , és ha a 3-SAT lehetséges legjobb futási ideje ilyen formájú lenne, akkor P nem lenne egyenlő NP-vel (mert a 3-SAT NP-teljes probléma, és ez az idő nem polinom), de az exponenciális idősejtés rossz lenne. $O(2^{n^{c)))$ $c<1$

A parametrikus komplexitáselméletben, mivel az exponenciális idő hipotézis azt jelenti, hogy nincs fix-parametrikusan eldönthető algoritmus a legnagyobb klikk megtalálására, ez azt is jelenti, hogy W[1] ≠ FPT [8] . Fontos nyitott probléma ezen a területen, megfordulhat-e ez a következmény – következik-e az exponenciális idősejtés? Létezik a parametrikus komplexitási osztályok hierarchiája, amelyet M-hierarchiának hívnak, és amely a W-hierarchiával van átszőve abban az értelemben, hogy minden i , . Például az a probléma, hogy egy n csúcsú gráfban egy adott méretű csúcsfedőt találjunk , M[1] esetén teljes. Az exponenciális időre vonatkozó sejtés ekvivalens azzal az állítással, hogy , és az i > 1 egyenlőség kérdése is nyitva marad [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]$

Megmutathatjuk a levezetést a másik irányba is, az exponenciális időre vonatkozó erős sejtés meghiúsulásától az elkülönített komplexitási osztályokig. Ahogy Williams [13] megmutatta , ha létezik olyan A algoritmus , amely megoldja a logikai időbeli kielégítési problémát valamilyen szuperpolinomiálisan növekvő függvényre , akkor a NEXPTIME nem a P/poly részhalmaza . Williams megmutatta, hogy ha létezik A algoritmus , és létezik egy sémacsalád, amely a NEXPTIME-ot szimulálja P/poly-ban, akkor az A algoritmus kombinálható egy olyan sémával, amely a NEXPTIME feladatokat nem determinisztikusan, rövidebb idő alatt modellezi, ami ellentmond az Időhierarchia tételnek . Így az A algoritmus létezése bizonyítja egy áramkör-család létezésének és e két komplexitási osztály szétválasztásának lehetetlenségét. $2^{n}/f(n)$ $f$

Jegyzetek

↑ Impagliazzo, Paturi, 1999 .
↑ 1 2 3 4 Woeginger, 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 .

Irodalom

Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia. Erős számítási alsó határok a paraméterezett komplexitáson keresztül // Journal of Computer and System Sciences. - 2006. - T. 72 , sz. 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. Paraméterezett algoritmusok. - Springer, 2015. - P. 555. - ISBN 978-3-319-21274-6 .
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk. Az EDGE CLIQUE COVER ismert algoritmusai valószínűleg optimálisak // Proc. 24. ACM-SIAM szimpózium a diszkrét algoritmusokról (SODA 2013) . - 2013. Archiválva : 2013. április 16.
Jevgenyij Dantsin, Alexander Wolpert. A kielégíthetőségi tesztelés elmélete és alkalmazásai – SAT 2010. Springer-Verlag, 2010. 6175. kötet . - S. 313-325 . - doi : 10.1007/978-3-642-14186-7_27 .
Uriel Feige , Joe Kilian. A korlátozott versus polinomiális nondeterminizmusról // Elméleti számítástechnika. - 1997. - 1. évf. 1 . - P. 1-20 .
Jörg Flum, Martin Grohe. 16. Szubexponenciális rögzített paraméterű követhetőség // Paraméterezett komplexitáselmélet . - Springer-Verlag, 2006. - S. 417 -451. - (EATCS szövegek az elméleti számítástechnikában). — ISBN 978-3-540-29952-3 .
Russell Impagliazzo, Ramamohan Paturi. A k-SAT összetettsége // Proc. 14. IEEE Conf. a számítási komplexitásról . - 1999. - S. 237-240. - doi : 10.1109/CCC.1999.766282 .
Russell Impagliazzo, Ramamohan Paturi, Francis Zane. Mely problémák erősen exponenciális összetettségűek? // Journal of Computer and System Sciences. - 2001. - T. 63 , sz. 4 . - S. 512-530 . - doi : 10.1006/jcss.2001.1774 .
Marek Karpinski, Schudy Warren. Gyorsabb algoritmusok visszacsatolási ívkészlet versenyhez, kemeny rangok összesítéséhez és közötti versenyhez // Proc. ISAAC 2010, I. rész - 2010. - P. 3-14 . - doi : 10.1007/978-3-642-17517-6_3 .
Daniel Lokshtanov, Daniel Marx, Saket Saurabh. A korlátos faszélességű gráfokon ismert algoritmusok valószínűleg optimálisak // Proc. 22. ACM/SIAM Szimpózium a diszkrét algoritmusokról (SODA 2011) . - 2011. - S. 777-789. Archiválva : 2012. október 18. a Wayback Machine -nál
Mihai Patraşcu, Ryan Williams. A gyorsabb SAT-algoritmusok lehetőségéről // Proc. 21. ACM/SIAM Szimpózium a diszkrét algoritmusokról (SODA 2010) . - 2010. - S. 1065-1075.
Ryan Williams. A kimerítő keresés javítása szuperpolinom alsó határokat von maga után // Proc. 42. ACM szimpózium a számítástechnikai elméletről (STOC 2010). - New York, NY, USA: ACM, 2010. - S. 231-240. - doi : 10.1145/1806689.1806723 .
Gerhard J. Woeginger. Pontos algoritmusok NP-nehéz problémákra: felmérés // Kombinatorikus optimalizálás — Eureka, You Shrink! . - Springer-Verlag, 2003. - T. 2570. - S. 185-207. - doi : 10.1007/3-540-36478-1_17 .