Exponentiell tidsförmodan

Den exponentiella tidsförmodan är ett obevisat antagande om beräkningskomplexitet som formulerades av Impagliazzo och Paturi [1] . Gissningen säger att 3-SAT (eller något av de relaterade NP-kompletta problemen) inte kan lösas i subexponentiell tid i värsta fall [2] . Av giltigheten av den exponentiella tidshypotesen, om den är sann, skulle det följa att P ≠ NP, men gissningen är ett starkare uttalande. Från uttalandet av hypotesen kan det visas att många beräkningsproblem är likvärdiga i komplexitet i den meningen att om en av dem har en exponentiell tidsalgoritm, så har de alla algoritmer av samma komplexitet.

Definition

Uppgiften k -SAT är uppgiften att kontrollera om ett booleskt uttryck i konjunktiv normal form som har fler än k variabler per (konjunktivt) uttryck kan göras sant genom att tilldela värdet av booleska värden till uttryckets variabler. För vilket heltal som helst definierar vi ett reellt tal som infimum av reella tal , för vilket det finns en algoritm för att lösa k -SAT-problemet i tid , där n är antalet variabler i detta k -SAT-problem. Sedan , eftersom 2-SAT problemet kan lösas i polynomtid . Den exponentiella tidshypotesen är antagandet att för någon . Det är tydligt att , så gissningen är likvärdig med antagandet att , positiviteten hos de återstående siffrorna följer automatiskt av antagandet. $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))$

Vissa källor definierar den exponentiella tidsförmodan som ett något svagare påstående att 3-SAT inte kan lösas i tid . Om det finns en algoritm för att lösa 3-SAT-problemet i tid , är det klart att det kommer att vara lika med noll. Detta överensstämmer dock med nuvarande kunskap om att det kan finnas en sekvens av 3-SAT-algoritmer, som var och en går i tid för siffror som tenderar till noll, men beskrivningen av dessa algoritmer växer snabbt så att en enda algoritm inte kan välja och köra automatiskt den mest lämpliga algoritmen [3] . $2^{o(n)}$ $2^{o(n)}$ ${\displaystyle s_{3))$ $O(2^{\delta _{i}n})$ $\delta _{i}$

Eftersom siffrorna bildar en monoton sekvens , som är avgränsad från ovan av en, måste de konvergera till gränsen . Den starka exponentiella tidsförmodan (SETH) är antagandet att gränsvärdet s ∞ för en talföljd s k är lika med ett [4] . $s_{3},s_{4},\ldots$ ${\displaystyle s_{\infty ))$

En annan version av gissningen är den heterogena exponentiella tidsförmodan , som stärker den andra delen av ETH, som postulerar att det inte finns någon familj av algoritmer (en för varje inmatningslängd i andan av hint ) som kan lösa de 3- SAT problem i tid 2 o( n ) .

Tillfredsställelse följd

Kan inte vara lika för något ändligt k — som Impagliazzo, Paturi och Zane [5] har visat , det finns en konstant sådan att . Därför, om hypotesen om exponentiell tid är sann, måste det finnas oändligt många värden på k för vilka s k skiljer sig från . ${\displaystyle s_{k))$ ${\displaystyle s_{\infty ))$ $\alfa$ $s_{k}\leqslant s_{\infty }(1-\alpha /k)$ $s_{k+1}$

Ett viktigt verktyg inom detta område är glesmaheten hos Impagliazzo, Paturi och Zane [5] , som visar att för vilken k - CNF-formel som helst kan ersättas med enklare k -CNF-formler där varje variabel endast förekommer ett konstant antal av gånger, så antalet meningar är linjärt. Sparsitetslemma bevisas genom att successivt hitta stora uppsättningar uttryck som har en icke-tom gemensam skärningspunkt i en given formel, och ersätta formeln med två enklare formler, i en av vilka varje sådant uttryck ersätts med deras gemensamma skärningspunkt, och i den andra skärningen tas bort från varje uttryck. Genom att tillämpa det glesa lemmat och använda nya variabler för att dela uttryck, kan man få en uppsättning 3-CNF-formler, var och en med ett linjärt antal variabler, så att den ursprungliga k -CNF-formeln är tillfredsställbar om och endast om minst en av dessa 3-CNF-formler är möjliga. Således, om 3-SAT kunde lösas i sub-exponentiell tid, kan man använda denna reduktion för att lösa k - SAT-problemet i sub-exponentiell tid. På motsvarande sätt, om för någon k > 3, så är den exponentiella tidsförmodan också sann [2] [5] . $\epsilon > 0$ $O(2^{{\epsilon }n})$ $O(2^{\epsilon }n)$ $s_{k}>0$ $s_{3}>0$

Gränsvärdet för talföljden s k överstiger inte s CNF , där s CNF är infimum av tal så att tillfredsställelsen av formler i konjunktiv normalform utan att begränsa uttryckets längd kan lösas i tid . Således, om den starka exponentiella tidsförmodan är sann, så finns det ingen algoritm för det allmänna CNF-tillfredsställbarhetsproblemet som är väsentligt snabbare än att testa alla möjliga propositioner för sanning . Men om den starka gissningen om exponentiell tid inte är sann, är det fortfarande möjligt för s CNF att vara lika med ett [6] . ${\displaystyle s_{\infty ))$ $\delta$ $O(2:{{\delta }n})$

Konsekvenser för sökproblem

Den exponentiella tidsförmodan antyder att många andra problem i SNP komplexitetsklassen inte har algoritmer vars körtid är mindre än c n för någon konstant c . Dessa problem inkluderar graf k -färgbarhet , hitta Hamiltonska cykler , största klick , största oberoende uppsättningar och vertextäcker på grafer med n hörn. Omvänt, om något av dessa problem har en subexponentiell algoritm, kommer det att vara möjligt att visa att den exponentiella tidsförmodan är falsk [2] [5] .

Om klickar eller oberoende uppsättningar av logaritmisk storlek kunde hittas i polynomtid, skulle den exponentiella tidsförmodan vara fel. Således, även om det är osannolikt att hitta klicker eller oberoende uppsättningar av så liten storlek är NP-komplett, innebär den exponentiella tidsförmodan att dessa problem inte är polynomiska [2] [7] . Mer generellt innebär den exponentiella tidsförmodan att det är omöjligt att hitta klicker eller oberoende uppsättningar av storlek k i tiden [8] . Hypotesen om exponentiell tid innebär också att det är omöjligt att lösa problemet k -SUM (med tanke på n reella tal måste du hitta k av dem, vilket ger summan noll) i tid . Den starka exponentiella tidsförmodan antyder att det är omöjligt att hitta dominerande mängder bestående av k hörn på kortare tid än [6] . $n^{o(k)}$ $n^{o(k)}$ $n^{ko(1)}$

Det följer också av den exponentiella tidshypotesen att det viktade problemet med att hitta en cykelskärande uppsättning bågar i turneringar (FAST) inte har en parametrisk algoritm med löptid , det har inte ens en parametrisk algoritm med löptid [9] . $O^{*}(2^{o({\sqrt {OPT)))})$ $O^{*}(2^{O({\sqrt {OPT)))})$

Den starka exponentiella tidsförmodan leder till skarpa gränser för den parameteriserade komplexiteten för vissa problem på grafer med begränsad trädbredd . I synnerhet, om den starka exponentiella tidsförmodan är sann, är den optimala tidsgränsen för att hitta oberoende uppsättningar på grafer med trädbredd likaw [10] . På motsvarande sätt skulle varje förbättring av dessa körtider ogiltigförklara den starka exponentiella tidsförmodan [11] . Det följer också av den exponentiella tidshypotesen att varje fast-parametriskt avgörbar algoritm för att täcka kanterna på en graf med klick måste ha ett dubbelt exponentiellt beroende av parametern [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)}$

Implikationer i kommunikationskomplexitetsteori

I problemet med trepartsdisjunktion av mängder i kommunikationskomplexitet ges tre delmängder av heltal från något intervall [1, m ] och tre kommunicerande deltagare, som var och en känner till två av de tre delmängderna. Målet för deltagarna är att överföra så få bitar av information till varandra som möjligt över en gemensam kommunikationskanal, men så att en av deltagarna kan avgöra om skärningspunkten mellan de tre uppsättningarna är tom eller inte. Ett trivialt m -bit-protokoll skulle vara att skicka en av deltagarna i bitvektorn som beskriver skärningspunkten mellan två uppsättningar kända för honom, varefter var och en av de återstående två deltagarna kan bestämma korsningens tomhet. Men om det finns ett protokoll som löser problemet i o( m ) hopp och beräkningar, kan det konverteras till en k -SAT-algoritm i O(1,74 n ) tid för vilken fast konstant k som helst , vilket bryter mot den starka exponentiella tidshypotesen . Därför följer det av den starka gissningen om exponentiell tid att antingen det triviala protokollet för problemet med tredelad disjunktivitet av uppsättningar är optimalt, eller så kräver vilket bättre protokoll ett exponentiellt antal beräkningar [6] . $2^{o(m)}$

Konsekvenser i strukturell komplexitetsteori

Om den exponentiella tidshypotesen är korrekt, bör 3-SAT inte ha en polynomisk tidsalgoritm, och därför skulle det följa att P ≠ NP . I detta fall skulle 3-SAT-problemet inte ens ha en kvasipolynomisk tidsalgoritm , så NP kunde inte vara en delmängd av klassen QP. Men om den exponentiella tidsförmodan inte är sann, skulle det inte följa att klasserna P och NP är lika. Det finns NP-kompletta problem för vilka den mest kända lösningstiden är av formen för , och om bästa möjliga körtid för 3-SAT var av denna form, så skulle P inte vara lika med NP (eftersom 3-SAT är ett NP-komplett problem, och den här tiden är inte polynom), men den exponentiella tidsförmodan skulle vara fel. $O(2^{n^{c)))$ $c<1$

I parametrisk komplexitetsteori, eftersom den exponentiella tidshypotesen antyder att det inte finns någon fast-parametriskt avgörbar algoritm för att hitta den största klicken, innebär det också att W[1] ≠ FPT [8] . Är ett viktigt öppet problem inom detta område, kan detta följaktligen vända - följer den exponentiella tidsförmodan? Det finns en hierarki av parametriska komplexitetsklasser som kallas M-hierarkin, som är varvas med W-hierarkin i den meningen att för alla i , . Till exempel är problemet med att hitta ett vertextäcke av en storlek i en graf med n hörn komplett för M[1]. Gissningen om exponentiell tid motsvarar påståendet att , och frågan om jämlikhet för i > 1 också förblir öppen [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]$

Man kan också visa härledningen åt andra hållet, från misslyckandet i den starka gissningen om exponentiell tid till separata komplexitetsklasser. Som Williams [13] visade , om det finns en algoritm A som löser det booleska tidstillfredsställelseproblemet för någon superpolynomiellt växande funktion , så är NEXPTIME inte en delmängd av P/poly . Williams visade att om Algoritm A existerar och en familj av scheman som simulerar NEXPTIME i P/poly också existerar, så skulle algoritm A kunna kombineras med ett schema för att modellera NEXPTIME-uppgifter icke-deterministiskt på kortare tid, vilket motsäger Time Hierarchy Theorem . Således bevisar existensen av algoritm A omöjligheten av existensen av en familj av kretsar och separationen av dessa två komplexitetsklasser. $2^{n}/f(n)$ $f$

Anteckningar

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

Litteratur

Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia. Starka beräkningsmässiga nedre gränser via parametriserad komplexitet // 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. Parameteriserade algoritmer. - Springer, 2015. - S. 555. - ISBN 978-3-319-21274-6 .
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk. Kända algoritmer för EDGE CLIQUE COVER är förmodligen optimala // Proc. 24:e ACM-SIAM-symposiet om diskreta algoritmer (SODA 2013) . - 2013. Arkiverad den 16 april 2013.
Evgeny Dantsin, Alexander Wolpert. Teori och tillämpningar av Satisfiability Testing–SAT 2010. Springer-Verlag, 2010. Vol. 6175 . - S. 313-325 . - doi : 10.1007/978-3-642-14186-7_27 .
Uriel Feige , Joe Kilian. Om begränsad kontra polynomisk nondeterminism // Teoretisk datavetenskap. - 1997. - Vol. 1 . - S. 1-20 .
Jörg Flum, Martin Grohe. 16. Subexponentiell spårbarhet med fasta parametrar // Parameteriserad komplexitetsteori . - Springer-Verlag, 2006. - S. 417 -451. - (EATCS Texts in Theoretical Computer Science). — ISBN 978-3-540-29952-3 .
Russell Impagliazzo, Ramamohan Paturi. Komplexiteten hos k-SAT // Proc. 14:e IEEE Conf. om beräkningskomplexitet . - 1999. - S. 237-240. - doi : 10.1109/CCC.1999.766282 .
Russell Impagliazzo, Ramamohan Paturi, Francis Zane. Vilka problem har starkt exponentiell komplexitet? // Tidskrift för data- och systemvetenskap. - 2001. - T. 63 , nr. 4 . - S. 512-530 . - doi : 10.1006/jcss.2001.1774 .
Marek Karpinski, Schudy Warren. Snabbare algoritmer för feedback Arc Set Tournament, Kemeny Rank Aggregation och Betweenness Tournament // Proc. ISAAC 2010, del I. - 2010. - S. 3-14 . - doi : 10.1007/978-3-642-17517-6_3 .
Daniel Lokshtanov, Daniel Marx, Saket Saurabh. Kända algoritmer på grafer för avgränsad trädbredd är förmodligen optimala // Proc. 22:a ACM/SIAM-symposiet om diskreta algoritmer (SODA 2011) . - 2011. - S. 777-789. Arkiverad 18 oktober 2012 på Wayback Machine
Mihai Patraşcu, Ryan Williams. Om möjligheten till snabbare SAT-algoritmer // Proc. 21:a ACM/SIAM-symposiet om diskreta algoritmer (SODA 2010) . - 2010. - S. 1065-1075.
Ryan Williams. Förbättring av uttömmande sökning innebär superpolynomiska nedre gränser // Proc. 42:a ACM Symposium on Theory of Computing (STOC 2010). - New York, NY, USA: ACM, 2010. - S. 231-240. - doi : 10.1145/1806689.1806723 .
Gerhard J. Woeinger. Exakta algoritmer för NP-hårda problem: En undersökning // Combinatorial Optimization — Eureka, You Shrink! . - Springer-Verlag, 2003. - T. 2570. - S. 185-207. - doi : 10.1007/3-540-36478-1_17 .