Exponentiell tidshypotes

I beräkningskomplexitetsteorin är den exponentiella tidshypotesen ett obevisat antagande om beräkningshårdhet som formulerades av Impagliazzo & Paturi (1999) . Den anger att tillfredsställelsen av 3-CNF booleska formler inte kan lösas snabbare än exponentiell tid i värsta fall . Den exponentiella tidshypotesen, om sann, skulle antyda att P ≠ NP , men det är ett starkare påstående. Det antyder att många beräkningsproblem är likvärdiga i komplexitet, i den meningen att om en av dem har en subexponentiell tidsalgoritm så har de alla det, och att många kända algoritmer för dessa problem har optimal eller nästan optimal tidskomplexitet .

Definition

k $k$ -SAT- problemet är en version av det booleska tillfredsställbarhetsproblemet där indata till problemet är ett booleskt uttryck i konjunktiv normal form det vill säga en och ellers av variabler och deras negationer) med högst $k$ variabler per sats. Målet är att avgöra om detta uttryck kan göras för att vara sant genom någon tilldelning av booleska värden till dess variabler. 2-SAT har en linjär tidsalgoritm , men alla kända algoritmer för större $k$ tar exponentiell tid , med basen för exponentialfunktionen beroende av $k$ . Till exempel WalkSAT probabilistiska algoritm lösa $k$ -SAT i genomsnittlig tid

$$\left(2-{\frac {2}{k}}\right)^{n}n^{O(1)},$$

där $n$ är antalet variabler i den givna $k$ -SAT -instansen. För varje heltal $k\geq 3$ , definiera $s_{k}$ som det minsta talet så att $k$ -SAT kan lösas i tiden $2^{s_{k}n+o(n)}$ . Detta minimum kanske inte existerar om en sekvens av bättre och bättre algoritmer har motsvarande mindre exponentiell tillväxt i sina tidsgränser; i så fall, definiera $s_{k}$ till att vara infimum av de reella talen $\delta$ för vilka $k$ -SAT kan lösas i tiden $O(2^{\delta n})$ . Eftersom problem med större $k$ inte kan vara enklare, ordnas dessa nummer som $s_{3}\leq s_{4}\leq \cdots$ , och på grund av WalkSAT är högst

$$s_{k}\leq \log _{2}\left(2-{\frac {2}{k}}\right)<1 .$$

Den exponentiella tidshypotesen är gissningen att de alla är icke-noll, eller motsvarande, att den minsta av dem, $s_{3}$ , är icke-noll.

Vissa källor definierar den exponentiella tidshypotesen som det något svagare påståendet att 3-SAT inte kan lösas i tiden $2^{o(n)}$ . Om det fanns en algoritm för att lösa 3-SAT i tiden $2^{o(n)}$ , då skulle $s_{3}$ vara lika med noll. Det överensstämmer dock med nuvarande kunskap att det kan finnas en sekvens av 3-SAT-algoritmer, var och en med körtid $O(2^{\delta _{i}n})$ för en talföljd $\delta _{i}$ som tenderar mot noll, men där beskrivningarna av dessa algoritmer växer så snabbt att en enda algoritm inte automatiskt kunde välja och köra den mest lämpliga. Om detta skulle vara fallet, då $s_{3}$ vara lika med noll även om det inte skulle finnas någon enskild algoritm som körs i tiden $2^{o(n)}$ . En relaterad variant av den exponentiella tidshypotesen är den olikformiga exponentiella tidshypotesen , som antyder att det inte finns någon familj av algoritmer (en för varje längd av ingången, i rådens anda) som kan lösa 3-SAT i tid $2^{o(n)}$ .

Eftersom talen $s_{3},s_{4},\dots$ bildar en monoton sekvens som är avgränsad ovanför av ett, måste de konvergera till en gräns

$$s_{\infty }=\lim _{k\to \infty }s_{k}.$$

Den starka exponentiella tidshypotesen (SETH) är gissningen att $s_{\infty }=1$ .

Implikationer

Tillfredsställelse

Det är inte möjligt för $s_{k}$ att vara lika med $s_{\infty }$ för någon ändlig $k$ : som Impagliazzo, Paturi & Zane (2001) visade, där existerar en konstant $\alpha$ så att $s_{k}\leq s_{\infty }(1-\alpha /k)$ . Därför, om den exponentiella tidshypotesen är sann, måste det finnas oändligt många värden på $k$ för vilka $s_{k}$ skiljer sig från $s_{k+1}$ .

varje ${\displaystyle \varepsilon >0} kan$ inom detta område är sparsifieringslemmat från Impagliazzo, Paturi & Zane (2001), som visar att för vilken $k$ -CNF- formel som helst ersättas av $O(2^{\varepsilon n})$ enklare $k$ -CNF -formler där varje variabel endast förekommer ett konstant antal gånger, och därför där antalet satser är linjära. Sparsifieringslemmat bevisas genom att upprepade gånger hitta stora uppsättningar av satser som har en icke-tom gemensam skärningspunkt i en given formel, och ersätta formeln med två enklare formler, av vilka en har var och en av dessa satser ersatt med sin gemensamma skärningspunkt och den andra av vilka har skärningspunkten borttagen från varje klausul. Genom att tillämpa sparsifieringslemmat och sedan använda nya variabler för att dela upp satserna kan man sedan få en uppsättning $O(2^{\varepsilon n})$ 3-CNF-formler, var och en med en 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 tillfredsställbar. Därför, om 3-SAT kunde lösas i subexponentiell tid, skulle man kunna använda denna reduktion för att lösa $k$ -SAT i subexponentiell tid också. På motsvarande sätt, om $s_{k}>0$ för valfri ${\displaystyle k>0} ,$ då s $\displaystyle s_{3}>0}$ också, och den exponentiella tidshypotesen skulle vara sant.

Begränsningsvärdet $s_{\infty }$ för talföljden $s_{k}$ är högst lika med $s_{\operatörsnamn {CNF} }$ , där $s_{\operatörsnamn {CNF} }$ är infimum av talen $\delta$ så att tillfredsställelsen av konjunktiva normalformsformler utan satslängdsgränser kan lösas i tiden $O(2^{\delta n})$ . Därför, om den starka exponentiella tidshypotesen är sann, skulle det inte finnas någon algoritm för allmän CNF-tillfredsställelse som är betydligt snabbare än en brute-force-sökning över alla möjliga sanningstilldelningar . Men om den starka exponentiella tidshypotesen misslyckas, skulle det fortfarande vara möjligt för $s_{\operatörsnamn {CNF} }$ att vara lika med ett.

Andra sökproblem

Den exponentiella tidshypotesen innebär att många andra problem i komplexitetsklassen SNP inte har algoritmer vars körtid är snabbare än $c^{n}$ för någon konstant $c$ . Dessa problem inkluderar grafens k -färgbarhet , att hitta Hamiltonska cykler , maximala klick , maximala oberoende uppsättningar och vertextäckning på $n$ -vertexgrafer . Omvänt, om något av dessa problem har en subexponentiell algoritm, kan den exponentiella tidshypotesen visa sig vara falsk.

Om klicker eller oberoende uppsättningar av logaritmisk storlek kunde hittas i polynomtid, skulle den exponentiella tidshypotesen vara falsk. Därför, även om det är osannolikt att det är NP-komplett att hitta klicker eller oberoende uppsättningar av så liten storlek, innebär den exponentiella tidshypotesen att dessa problem är icke-polynomiska. Mer generellt innebär den exponentiella tidshypotesen att det inte är möjligt att hitta klicker eller oberoende uppsättningar av storleken $k$ i tiden $n^{o(k)}$ . Den exponentiella tidshypotesen innebär också att det inte är möjligt att lösa problemet k -SUM (med $n$ reella tal, hitta $k$ av dem som adderas till noll) i tiden $n^{o(k)}$ . Den starka exponentiella tidshypotesen innebär att det inte är möjligt att hitta $k$ -vertexdominerande mängder snabbare än i tiden $n^{ko(1)}$ .

Den exponentiella tidshypotesen innebär också att det viktade återkopplingsbåguppsättningsproblemet i turneringar inte har en parametriserad algoritm med löptid O $\textstyle O(2^{o({\sqrt) {\operatörsnamn {OPT} }})}n^{O(1)})}$ . Den har dock en parametriserad algoritm med körtid O $\textstyle O(2^{O({\sqrt {\operatörsnamn {OPT} }})}n^{O (1)})}$ .

Den starka exponentiella tidshypotesen leder till snäva gränser för den parametriserade komplexiteten hos flera grafproblem på grafer med begränsad trädbredd . I synnerhet, om den starka exponentiella tidshypotesen är sann, är den optimala tidsgränsen för att hitta oberoende uppsättningar på grafer av trädbredden ${\textstyle { \bigl (}2-o(1){\bigr )}^{w}n^{O(1)}} , den optimala tiden$ för w $\displaystyle w}$ det dominerande mängdproblemet är ${\textstyle {\bigl (}3-o(1){\bigr )}^{w}n^{O(1)}} , den optimala tiden$ för maximal skärning är ${\textstyle {\bigl (}2-o(1){\bigr )}^{w}n^{O(1)}} och$ den optimala tiden för $k$ -färgning är ${\textstyle {\bigl (}ko(1){\bigr )}^{w}n^{O(1)}}$ . På motsvarande sätt skulle varje förbättring av dessa löptider falsifiera den starka exponentiella tidshypotesen . Den exponentiella tidshypotesen antyder också att varje algoritm med fasta parametrar för kantklicktäckning måste ha dubbelt exponentiellt beroende av parametern.

Kommunikationskomplexitet

I trepartsuppsättningens disjointnessproblem i kommunikationskomplexitet specificeras tre delmängder av heltal i något område ${\displaystyle [1,m]} , och tre kommunicerande parter känner vardera till två av de tre delmängderna.$ Målet är att parterna ska sända så få bitar till varandra på en delad kommunikationskanal för att en av parterna ska kunna avgöra om skärningspunkten mellan de tre uppsättningarna är tom eller icke-tom. Ett trivialt $m$ -bit kommunikationsprotokoll skulle vara för en av de tre parterna att sända en bitvektor som beskriver skärningspunkten mellan de två uppsättningarna kända för den parten, varefter någon av de två återstående parterna kan bestämma tomheten i genomskärning. Men om det finns ett protokoll som löser problemet med ${\displaystyle o(m)}-$ kommunikation och ${\displaystyle 2^{o(m)}}-$ beräkning, kan det omvandlas till en algoritm för att lösa $k$ -SAT i tiden $O(1.74^{n})$ för vilken fast konstant ${\displaystyle k} som helst$ , vilket bryter mot den starka exponentiella tidshypotesen. Därför innebär den starka exponentiella tidshypotesen antingen att det triviala protokollet för trepartsuppsättningsskillnad är optimalt, eller att vilket bättre protokoll som helst kräver en exponentiell mängd beräkning .

Strukturell komplexitet

Om den exponentiella tidshypotesen är sann, så skulle 3-SAT inte ha en polynomisk tidsalgoritm, och därför skulle det följa att P ≠ NP . Mer starkt, i det här fallet kunde 3-SAT inte ens ha en kvasipolynomisk tidsalgoritm , så NP kunde inte vara en delmängd av QP. Men om den exponentiella tidshypotesen misslyckas, skulle det inte ha någon betydelse för P kontra NP-problemet. Ett utfyllnadsargument bevisar förekomsten av NP-kompletta problem för vilka de mest kända körtiderna har formen ${\textstyle O(2^{n^{c}})}$ för $c<1$ , och om den bästa möjliga körtiden för 3-SAT var av denna form, så skulle P vara olikvärdig med NP (eftersom 3-SAT är NP-komplett och denna tidsbundna inte är polynom) men den exponentiella tidshypotesen skulle vara falskt.

I parameteriserad komplexitetsteori, eftersom den exponentiella tidshypotesen antyder att det inte existerar en algoritm som kan hanteras med fasta parametrar för maximal klick, innebär det också att W[1] ≠ FPT . Det är ett viktigt öppet problem inom detta område om denna implikation kan vändas: implicerar W[1] ≠ FPT den exponentiella tidshypotesen? Det finns en hierarki av parametriserade komplexitetsklasser som kallas M-hierarkin som interfolierar W-hierarkin i den meningen att för alla $i$ , ${ \displaystyle {\mathsf {M}}[i]\subseteq {\mathsf {W}}[i]\subseteq {\mathsf {M}}[i+1]}$ ; till exempel är problemet med att hitta ett vertextäcke med storleken $k\log n$ i en $n$ -vertexgraf med parametern $k$ komplett för M[1] . Den exponentiella tidshypotesen är ekvivalent med påståendet att M[1] ≠ FPT , och frågan om ${\mathsf {M}}[i]\subseteq {\mathsf { W}}[i]$ för $i>1$ är också öppen.

Det är också möjligt att bevisa implikationer i den andra riktningen, från misslyckandet av en variation av den starka exponentiella tidshypotesen till separationer av komplexitetsklasser. Som Williams (2010) visar, om det finns en algoritm $A$ som löser den booleska kretsens tillfredsställelse i tiden $2^{n}/f(n)$ för vissa superpolynomiellt växande funktion $f$ , då är NEXPTIME inte en delmängd av P/poly . Williams visar att om algoritm $A$ existerar, och en familj av kretsar som simulerar NEXPTIME i P/poly också existerade, så skulle algoritm $A$ kunna sammansättas med kretsarna för att simulera NEXPTIME-problem icke-deterministiskt i en mindre tid, vilket bryter mot tidshierarkisatsen . Därför bevisar förekomsten av algoritm $A$ att familjen av kretsar inte existerar och separeringen av dessa två komplexitetsklasser .

Se även

• Savitchs teorem , som visar att ett liknande exponentiellt gap inte kan hålla för rymdkomplexitet

Vidare läsning

•   Dantsin, Evgeny; Wolpert, Alexander (2010), "On moderatly exponential time for SAT", Theory and Applications of Satisfiability Testing–SAT 2010 , Lecture Notes in Computer Science, vol. 6175, Springer-Verlag, s. 313–325, doi : 10.1007/978-3-642-14186-7_27 , ISBN 978-3-642-14185-0