Exponenciální časová domněnka

Exponenciální časová domněnka je neprokázaný předpoklad o výpočetní složitosti , který formulovali Impagliazzo a Paturi [1] . Dohad říká, že 3-SAT (nebo jakýkoli ze souvisejících NP-úplných problémů) nelze v nejhorším případě vyřešit v sub- exponenciálním čase [2] . Platnost exponenciální časové domněnky, je-li pravdivá, by znamenala, že P ≠ NP , ale domněnka je silnější tvrzení. Z prohlášení hypotézy lze ukázat, že mnoho výpočetních problémů je ekvivalentních co do složitosti v tom smyslu, že pokud má jeden z nich exponenciální časový algoritmus, pak všechny mají algoritmy stejné složitosti.

Definice

Úloha k -SAT je úkolem ověřit, zda booleovský výraz v konjunktivní normální formě , který má více než k proměnných na (konjunktivní) výraz, lze provést přiřazením hodnoty booleovských hodnot proměnným výrazu. Pro libovolné celé číslo definujeme reálné číslo jako infimum reálných čísel , pro které existuje algoritmus pro řešení problému k -SAT v čase , kde n je počet proměnných v tomto problému k -SAT. Potom , protože problém 2-SAT lze vyřešit v polynomiálním čase . Exponenciální časová hypotéza je předpoklad , že pro jakýkoli . Je jasné, že , takže domněnka je ekvivalentní předpokladu, že , kladnost zbývajících čísel vyplývá automaticky z předpokladu. $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))$

Některé zdroje definují exponenciální časový dohad jako o něco slabší tvrzení, že 3-SAT nelze řešit v čase . Pokud existuje algoritmus pro řešení problému 3-SAT v čase , pak je jasné, že se bude rovnat nule. To je však v souladu se současnými znalostmi, že může existovat sekvence 3-SAT algoritmů, z nichž každý běží v čase pro čísla inklinující k nule, ale popis těchto algoritmů rychle roste, takže jediný algoritmus není schopen automaticky vybrat a spustit nejvhodnější algoritmus [3] . $2^{o(n)}$ $2^{o(n)}$ ${\displaystyle s_{3))$ $O(2^{\delta _{i}n})$ $\delta _{i}$

Protože čísla tvoří monotónní posloupnost , která je shora ohraničena jedničkou, musí konvergovat k limitě . Silný exponenciální časový odhad (SETH) je předpoklad, že limitní hodnota s ∞ posloupnosti čísel s k je rovna jedné [4] . $s_{3},s_{4},\ldots$ ${\displaystyle s_{\infty ))$

Další verzí domněnky je heterogenní exponenciální časová domněnka , která posiluje druhou část ETH, která předpokládá, že neexistuje žádná rodina algoritmů (jeden pro každou délku vstupu v duchu hint ), které by dokázaly vyřešit 3- Problém SAT v čase 2 o( n ) .

Důsledek splnitelnosti

Nemůže se rovnat pro žádné konečné k — jak ukázali Impagliazzo, Paturi a Zane [5] , existuje konstanta taková, že . Pokud je tedy hypotéza exponenciálního času pravdivá, musí existovat nekonečně mnoho hodnot k , pro které se s k liší od . ${\displaystyle s_{k))$ ${\displaystyle s_{\infty ))$ $\alpha$ $s_{k}\leqslant s_{\infty }(1-\alpha /k)$ $s_{k+1}$

Důležitým nástrojem v této oblasti je lemma řídkosti Impagliazzo, Paturi a Zane [5] , které ukazuje, že pro jakýkoli k -CNF vzorec může být nahrazen jednoduššími k -CNF formulemi, ve kterých se každá proměnná objevuje pouze jako konstantní počet krát, a tak je počet vět lineární. Lemma řídkosti se dokazuje postupným hledáním velkých množin výrazů, které mají v daném vzorci neprázdný společný průnik, a nahrazením vzorce dvěma jednoduššími formulemi, z nichž jeden je každý takový výraz nahrazen svým společným průnikem, a v druhý průsečík je z každého výrazu odstraněn. Aplikací řídkého lemmatu a použitím nových proměnných k rozdělení výrazů lze získat sadu 3-CNF vzorců, z nichž každý má lineární počet proměnných, takže původní vzorec k - CNF je splnitelný tehdy a pouze tehdy, pokud alespoň jedna z tyto 3-CNF vzorce jsou proveditelné. Pokud by tedy 3-SAT mohl být vyřešen v subexponenciálním čase, lze tuto redukci použít k vyřešení problému k - SAT v subexponenciálním čase. Ekvivalentně, jestliže pro jakékoli k > 3, pak platí i exponenciální časová domněnka [2] [5] . $\epsilon > 0$ $O(2^{{\epsilon }n})$ $O(2^{\epsilon }n)$ $s_{k}>0$ $s_{3}>0$

Mezní hodnota posloupnosti čísel sk nepřesahuje s CNF , kde s CNF je takové infimum čísel , aby bylo možné v čase vyřešit splnitelnost vzorců v konjunktivním normálním tvaru bez omezení délky výrazu . Pokud je tedy silná exponenciální časová domněnka pravdivá, pak neexistuje žádný algoritmus pro obecný problém splnitelnosti CNF, který by byl podstatně rychlejší než testování všech možných tvrzení na pravdivost . Pokud však silná domněnka o exponenciálním čase není pravdivá, zůstává možné, aby s CNF byl roven jedné [6] . ${\displaystyle s_{\infty ))$ $\delta$ $O(2:{{\delta }n})$

Důsledky problémů s vyhledáváním

Exponenciální časová domněnka implikuje, že mnoho dalších problémů ve třídě složitosti SNP nemá algoritmy, jejichž doba běhu je menší než c n pro nějakou konstantu c . Tyto problémy zahrnují k -barvitelnost grafu , nalezení Hamiltonových cyklů , největší kliky , největší nezávislé množiny a kryty vrcholů na grafech s n vrcholy. Naopak, pokud má některý z těchto problémů subexponenciální algoritmus, pak bude možné ukázat, že exponenciální časová domněnka je nepravdivá [2] [5] .

Pokud by bylo možné najít kliky nebo nezávislé množiny logaritmické velikosti v polynomiálním čase, exponenciální časová domněnka by byla špatná. I když je tedy nepravděpodobné, že by nalezení klik nebo nezávislých souborů tak malé velikosti bylo NP-úplné, exponenciální časová domněnka implikuje, že tyto problémy nejsou polynomiální [2] [7] . Obecněji, exponenciální časová domněnka implikuje, že je nemožné najít kliky nebo nezávislé množiny velikosti k v čase [8] . Hypotéza exponenciálního času také implikuje, že je nemožné vyřešit problém k -SUM (když je dáno n reálných čísel, musíte jich najít k a dát součet nula) v čase . Silná exponenciální časová domněnka implikuje, že je nemožné najít dominující množiny skládající se z k vrcholů za méně než čas [6] . $n^{o(k)}$ $n^{o(k)}$ $n^{ko(1)}$

Z exponenciální časové hypotézy také vyplývá, že vážený problém nalezení cyklicky řezající sady oblouků v turnajích (FAST) nemá parametrický algoritmus s dobou běhu , nemá dokonce ani parametrický algoritmus s dobou běhu [9] . $O^{*}(2^{o({\sqrt {OPT)))})$ $O^{*}(2^{O({\sqrt {OPT)))})$

Silná exponenciální časová domněnka vede k ostrým hranicím parametrizované složitosti některých problémů na grafech s omezenou šířkou stromu . Zejména, pokud je silný exponenciální časový odhad pravdivý, pak se optimální časová hranice pro nalezení nezávislých množin na grafech se rovnáwšířkou stromu [10] . Ekvivalentně by jakékoli zlepšení těchto provozních časů zneplatnilo silný exponenciální časový odhad [11] . Z hypotézy exponenciálního času také vyplývá, že jakýkoli pevně-parametricky rozhoditelný algoritmus pro pokrytí hran grafu klikami musí mít dvojitou exponenciální závislost na parametru [12] . $(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)}$

Implikace v teorii komunikační složitosti

V problému tripartitní disjunktnosti množin v komunikační složitosti jsou dány tři podmnožiny celých čísel z nějakého intervalu [1, m ] a tři komunikující účastníci, z nichž každý zná dvě ze tří podmnožin. Cílem účastníků je přenést mezi sebou co nejméně bitů informací společným komunikačním kanálem, ale tak, aby jeden z účastníků mohl určit, zda je průsečík tří množin prázdný či nikoli. Triviálním m -bitovým protokolem by bylo poslat jednoho z účastníků bitového vektoru popisujícího průnik dvou jemu známých množin, načež každý ze zbývajících dvou účastníků může určit prázdnotu průniku. Pokud však existuje protokol, který řeší problém v o( m ) skocích a výpočtech, lze jej převést na algoritmus k -SAT v čase O(1,74 n ) pro jakoukoli pevnou konstantu k , což porušuje hypotézu silné exponenciální doby. . Ze silného dohadu o exponenciálním čase tedy vyplývá, že buď je optimální triviální protokol pro problém tripartitní disjunktivity množin, nebo jakýkoli lepší protokol vyžaduje exponenciální počet výpočtů [6] . $2^{o(m)}$

Důsledky v teorii strukturní složitosti

Pokud je exponenciální časová hypotéza správná, pak 3-SAT by neměl mít polynomiální časový algoritmus, a tak by z toho vyplývalo, že P ≠ NP . Ještě silněji, v tomto případě by problém 3-SAT neměl ani kvazi-polynomiální časový algoritmus , takže NP nemůže být podmnožinou třídy QP. Pokud však exponenciální časová domněnka není pravdivá, neznamená to, že třídy P a NP jsou si rovny. Existují NP-úplné problémy, pro které je nejznámější doba řešení ve tvaru pro , a pokud by nejlepší možný průběh pro 3-SAT byl v tomto tvaru, pak by se P nerovnalo NP (protože 3-SAT je NP-úplný problém a tento čas není polynomiální), ale exponenciální časová domněnka by byla chybná. $O(2^{n^{c)))$ $c<1$

V parametrické teorii složitosti, protože hypotéza exponenciálního času implikuje, že neexistuje žádný pevně-parametricky rozhoditelný algoritmus pro nalezení největší kliky, také implikuje, že W[1] ≠ FPT [8] . Je důležitý otevřený problém v této oblasti, může se tento důsledek obrátit - následuje exponenciální časová domněnka? Existuje hierarchie tříd parametrické složitosti zvaná M-hierarchie, která je proložena W-hierarchií v tom smyslu, že pro všechny i , . Například problém najít vrcholové pokrytí velikosti v grafu s n vrcholy je pro M[1] kompletní. Dohad o exponenciálním čase je ekvivalentní tvrzení, že , a otázka rovnosti pro i > 1 také zůstává otevřená [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]$

Odvození lze ukázat i opačným směrem, od selhání silné domněnky o exponenciálním čase až po samostatné třídy složitosti. Jak ukázal Williams [13] , pokud existuje algoritmus A , který řeší problém Booleovské časové splnitelnosti pro nějakou superpolynomiálně rostoucí funkci , pak NEXPTIME není podmnožinou P/poly . Williams ukázal, že pokud existuje Algoritmus A a existuje také rodina schémat simulujících NEXPTIME v P/poly, pak by Algoritmus A mohl být kombinován se schématem pro modelování úloh NEXPTIME nedeterministicky v kratším čase, což je v rozporu s teorémem časové hierarchie . Existence Algoritmu A tedy dokazuje nemožnost existence rodiny obvodů a oddělení těchto dvou tříd složitosti. $2^{n}/f(n)$ $F$

Poznámky

↑ 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 .

Literatura

Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia. Silné výpočetní dolní meze prostřednictvím parametrizované složitosti // Journal of Computer and System Sciences. - 2006. - T. 72 , č. 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. Parametrizované algoritmy. - Springer, 2015. - S. 555. - ISBN 978-3-319-21274-6 .
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk. Známé algoritmy pro EDGE CLIQUE COVER jsou pravděpodobně optimální // Proc. 24. ACM-SIAM Symposium on Discrete Algorithms (SODA 2013) . - 2013. Archivováno 16. dubna 2013.
Jevgenij Dantsin, Alexander Wolpert. Teorie a aplikace testování uspokojivosti – SAT 2010. Springer-Verlag, 2010. svazek 6175 . - S. 313-325 . - doi : 10.1007/978-3-642-14186-7_27 .
Uriel Feige , Joe Kilian. O omezeném versus polynomiálním nedeterminismu // Teoretická informatika. - 1997. - Sv. 1 . - str. 1-20 .
Jörg Flum, Martin Grohe. 16. Subexponenciální trasovatelnost s pevnými parametry // Teorie parametrizované složitosti . - Springer-Verlag, 2006. - S. 417 -451. - (EATCS Texty v teoretické informatice). — ISBN 978-3-540-29952-3 .
Russell Impagliazzo, Ramamohan Paturi. Složitost k-SAT // Proc. 14. IEEE Conf. o výpočetní složitosti . - 1999. - S. 237-240. - doi : 10.1109/CCC.1999.766282 .
Russell Impagliazzo, Ramamohan Paturi, Francis Zane. Které problémy mají silně exponenciální složitost? // Journal of Computer and System Sciences. - 2001. - T. 63 , no. 4 . - S. 512-530 . - doi : 10.1006/jcss.2001.1774 .
Marek Karpinski, Schudy Warren. Rychlejší algoritmy pro Feedback Arc Set Tournament, Kemeny Rank Agregation a Betweenness Tournament // Proc. ISAAC 2010, I. část - 2010. - S. 3-14 . - doi : 10.1007/978-3-642-17517-6_3 .
Daniel Lokshtanov, Daniel Marx, Saket Saurabh. Známé algoritmy na grafech omezené šířky stromu jsou pravděpodobně optimální // Proc. 22. ACM/SIAM Symposium on Discrete Algorithms (SODA 2011) . - 2011. - S. 777-789. Archivováno 18. října 2012 na Wayback Machine
Mihai Patraşcu, Ryan Williams. O možnosti rychlejších SAT algoritmů // Proc. 21. ACM/SIAM Symposium on Discrete Algorithms (SODA 2010) . - 2010. - S. 1065-1075.
Ryan Williams. Zlepšení vyčerpávajícího vyhledávání implikuje superpolynomiální dolní meze // Proc. 42. ACM Symposium on Theory of Computing (STOC 2010). - New York, NY, USA: ACM, 2010. - S. 231-240. - doi : 10.1145/1806689.1806723 .
Gerhard J. Woeginger. Přesné algoritmy pro NP-těžké problémy: Průzkum // Kombinatorická optimalizace — Eureka, You Shrink! . - Springer-Verlag, 2003. - T. 2570. - S. 185-207. - doi : 10.1007/3-540-36478-1_17 .