Exponentielle Zeithypothese - Exponential time hypothesis

In der rechnerischen Komplexitätstheorie ist die exponentielle Zeithypothese eine unbewiesene Annahme der rechnerischen Härte , die von Impagliazzo & Paturi (1999) formuliert wurde . Die Hypothese besagt, dass 3-SAT (oder eines von mehreren, aber nicht allen NP-vollständigen Problemen) im schlimmsten Fall nicht in subexponentieller Zeit gelöst werden kann . Die exponentielle Zeithypothese würde, falls zutreffend, implizieren, dass P ≠ NP ist , aber es ist eine stärkere Aussage. Es kann verwendet werden, um zu zeigen, dass viele Rechenprobleme in ihrer Komplexität gleichwertig sind, in dem Sinne, dass sie alle dies tun, wenn eines von ihnen einen subexponentiellen Zeitalgorithmus hat.

Definition

k -SAT ist das Problem des Testens, ob ein Boolescher Ausdruck in konjunktiver Normalform mit höchstens k Variablen pro Klausel durch Zuweisen von Booleschen Werten zu seinen Variablen als wahr gemacht werden kann. Definieren Sie für jede ganze Zahl k ≥ 2 eine reelle Zahl s k als das Infimum der reellen Zahlen δ, für die k -SAT in der Zeit O (2 δ n ) algorithmisch gelöst werden kann , wobei n die Anzahl der Variablen in der gegebenen ist k -SAT-Instanz. Dann ist s 2  = 0, weil 2-SAT in Polynomzeit gelöst werden kann . Darüber hinaus ist s 3  ≤  s 4  ≤ ..., da die Schwierigkeit mit zunehmendem k nicht abnimmt .

Die exponentielle Zeithypothese ist die Vermutung, dass s k  > 0 für jedes k  > 2 ist oder äquivalent, dass s 3  > 0 ist.

Einige Quellen definieren die exponentielle Zeithypothese als die etwas schwächere Aussage, dass 3-SAT nicht in der Zeit 2 o ( n ) gelöst werden kann . Wenn es einen Algorithmus bestanden 3-SAT zu lösen in der Zeit 2 O ( n ) , dann s 3 wäre gleich Null. Es stimmt jedoch mit dem aktuellen Wissen überein, dass es eine Folge von 3-SAT-Algorithmen geben könnte, von denen jeder eine Laufzeit O (2 δ i n ) für eine Folge von Zahlen δ i hat , die gegen Null tendieren, aber wo sich die Beschreibungen dieser Algorithmen befinden so schnell wachsend, dass ein einzelner Algorithmus den am besten geeigneten nicht automatisch auswählen und ausführen konnte.

Da die Zahlen s 3 , s 4 , ... eine monotone Folge bilden , die oben durch eins begrenzt ist, müssen sie gegen eine Grenze s ∞ konvergieren . Die starke exponentielle Zeithypothese (SETH) ist die Vermutung, dass s ∞ = 1 ist.

Eine andere Variante ist die ungleichmäßige exponentielle Zeithypothese , eine Verstärkung der zweiten Phrasierung der ETH, die besagt, dass es keine Familie von Algorithmen gibt (eine für jede Länge der Eingabe im Sinne eines Ratschlags ), die 3- lösen kann. SAT in Zeit 2 o ( n ) .

Implikationen für die Erfüllbarkeit

Es ist nicht möglich, dass s k für ein endliches k gleich s ∞ ist : Wie Impagliazzo, Paturi & Zane (2001) gezeigt haben, existiert eine Konstante α, so dass s k  ≤  s ∞ (1 -  α / k ) ist. Wenn die exponentielle Zeithypothese wahr ist, muss es daher unendlich viele Werte von k geben, für die sich s k von s k  + 1 unterscheidet .

Ein wichtiges Werkzeug in diesem Bereich ist das Sparsifikations-Lemma von Impagliazzo, Paturi & Zane (2001) , das zeigt, dass für jedes ε  > 0 jede k- CNF-Formel durch O (2 εn ) einfachere k- CNF-Formeln in ersetzt werden kann wobei jede Variable nur eine konstante Anzahl von Malen vorkommt und daher die Anzahl der Klauseln linear ist. Das Sparsifikations-Lemma wird bewiesen, indem wiederholt große Mengen von Klauseln gefunden werden, die in einer bestimmten Formel einen nicht leeren gemeinsamen Schnittpunkt haben, und die Formel durch zwei einfachere Formeln ersetzt wird, von denen eine jede dieser Klauseln durch ihre gemeinsame Schnittmenge ersetzt und die andere hat den Schnittpunkt aus jeder Klausel entfernt. Durch Anwenden des Sparsifikations-Lemmas und anschließendes Verwenden neuer Variablen zum Teilen der Klauseln kann dann ein Satz von O (2 & epsi ; n ) 3-CNF-Formeln mit jeweils einer linearen Anzahl von Variablen erhalten werden, so dass die ursprüngliche k- CNF-Formel erfüllt werden kann genau dann, wenn mindestens eine dieser 3-CNF-Formeln erfüllt werden kann. Wenn also 3-SAT in subexponentieller Zeit gelöst werden könnte, könnte man diese Reduktion verwenden, um k -SAT auch in subexponentieller Zeit zu lösen . Wenn s k  > 0 für jedes k  > 3 ist, dann ist auch s 3  > 0 und die exponentielle Zeithypothese wäre wahr.

Der Grenzwert s ∞ der Folge von Zahlen s k ist höchstens gleich s CNF , wobei s CNF das Infimum der Zahlen δ ist, so dass die Erfüllbarkeit von Formeln der konjunktiven Normalform ohne Klausellängenbegrenzungen in der Zeit O (2) gelöst werden kann δn ). Wenn daher die starke exponentielle Zeithypothese wahr ist, gibt es keinen Algorithmus für die allgemeine CNF-Erfüllbarkeit, der signifikant schneller ist als das Testen aller möglichen Wahrheitszuweisungen . Wenn jedoch die Hypothese der starken exponentiellen Zeit fehlschlägt, wäre es immer noch möglich, dass s CNF gleich eins ist.

Implikationen für andere Suchprobleme

Die exponentielle Zeithypothese impliziert, dass viele andere Probleme in der Komplexitätsklasse SNP keine Algorithmen haben, deren Laufzeit für eine Konstante  c schneller als c n ist . Diese Probleme umfassen die Färbbarkeit des Graphen k , das Finden von Hamilton-Zyklen , maximale Cliquen , maximale unabhängige Mengen und die Scheitelpunktabdeckung auf n- Vertex-Graphen. Wenn umgekehrt eines dieser Probleme einen subexponentiellen Algorithmus aufweist, könnte gezeigt werden, dass die exponentielle Zeithypothese falsch ist.

Wenn Cliquen oder unabhängige Mengen logarithmischer Größe in der Polynomzeit gefunden werden könnten, wäre die Hypothese der exponentiellen Zeit falsch. Obwohl es unwahrscheinlich ist, dass Cliquen oder unabhängige Mengen von solch kleiner Größe NP-vollständig sind, impliziert die exponentielle Zeithypothese, dass diese Probleme nicht polynomisch sind. Allgemeiner impliziert die exponentielle Zeithypothese, dass es nicht möglich ist, Cliquen oder unabhängige Mengen der Größe k in der Zeit n o ( k ) zu finden . Die exponentielle Zeithypothese impliziert auch, dass es nicht möglich ist, das k- SUM- Problem (wenn n reelle Zahlen gegeben sind, finde k davon, die zu Null addieren) in der Zeit n o ( k ) zu lösen . Die starke exponentielle Zeithypothese impliziert, dass es nicht möglich ist, k- Vertex-dominierende Mengen schneller als in der Zeit n k  -  o (1) zu finden .

Die exponentielle Zeithypothese impliziert auch, dass das Problem des gewichteten Feedback Arc Set Tournament (FAST) keinen parametrisierten Algorithmus mit der Laufzeit O * (2 o ( √ OPT ) ) hat, sondern einen parametrisierten Algorithmus mit der Laufzeit O * ( 2 O ( √ OPT ) ).

Die starke exponentielle Zeithypothese führt zu engen Grenzen für die parametrisierte Komplexität mehrerer Graphenprobleme in Graphen mit begrenzter Baumbreite . Insbesondere wenn die Hypothese der starken exponentiellen Zeit wahr ist, ist die optimale Zeit, die zum Finden unabhängiger Mengen in Graphen der Baumbreite w gebunden ist, (2 - o (1)) w n O (1) , die optimale Zeit für das Problem der dominierenden Menge ist (3 - o (1)) w n O (1) , die optimale Zeit für den maximalen Schnitt ist (2 - o (1)) w n O (1) und die optimale Zeit für die k- Färbung ist ( k - o (1)) w n O (1) . Entsprechend würde jede Verbesserung dieser Laufzeiten die starke exponentielle Zeithypothese verfälschen. Die exponentielle Zeithypothese impliziert auch, dass jeder nachvollziehbare Algorithmus mit festem Parameter für die Kantencliquenabdeckung eine doppelte exponentielle Abhängigkeit vom Parameter aufweisen muss.

Auswirkungen auf die Kommunikationskomplexität

In dem Drei-Parteien-Satz- Disjunktheitsproblem in der Kommunikationskomplexität werden drei Teilmengen der ganzen Zahlen in einem bestimmten Bereich [1, m ] angegeben, und drei kommunizierende Parteien kennen jeweils zwei der drei Teilmengen. Ziel ist es, dass die Parteien auf einem gemeinsam genutzten Kommunikationskanal möglichst wenige Bits untereinander übertragen, damit eine der Parteien feststellen kann, ob der Schnittpunkt der drei Sätze leer oder nicht leer ist. Ein triviales m- Bit-Kommunikationsprotokoll wäre, dass eine der drei Parteien einen Bitvektor überträgt , der den Schnittpunkt der beiden dieser Partei bekannten Sätze beschreibt, wonach eine der beiden verbleibenden Parteien die Leere des Schnittpunkts bestimmen kann. Wenn es jedoch ein Protokoll gibt, das das Problem mit der o ( m ) -Kommunikation und der 2 o ( m ) -Berechnung löst, könnte es in einen Algorithmus zum Lösen von k -SAT in der Zeit O (1,74 n ) für jede feste Konstante k umgewandelt werden. Verletzung der starken exponentiellen Zeithypothese. Daher impliziert die starke exponentielle Zeithypothese entweder, dass das triviale Protokoll für die Disjunktheit von Dreiparteienmengen optimal ist, oder dass jedes bessere Protokoll einen exponentiellen Rechenaufwand erfordert.

Auswirkungen auf die strukturelle Komplexität

Wenn die exponentielle Zeithypothese wahr ist, hätte 3-SAT keinen polynomiellen Zeitalgorithmus, und daher würde P ≠ NP folgen . In diesem Fall könnte 3-SAT nicht einmal einen quasi-polynomiellen Zeitalgorithmus haben, so dass NP keine Teilmenge von QP sein könnte. Wenn jedoch die Exponentialzeithypothese fehlschlägt, hat dies keine Auswirkungen auf das P-NP-Problem. Es gibt NP-vollständige Probleme, für die die bekanntesten Laufzeiten die Form O (2 n c ) für c  <1 haben, und wenn die bestmögliche Laufzeit für 3-SAT von dieser Form wäre, wäre P ungleich NP (weil 3-SAT NP-vollständig ist und diese Zeitgrenze nicht polynomisch ist), aber die exponentielle Zeithypothese wäre falsch.

In der parametrisierten Komplexitätstheorie impliziert W [1] ≠ FPT , da die Exponentialzeithypothese impliziert, dass es keinen Algorithmus mit festen Parametern für die maximale Clique gibt . In diesem Bereich ist es ein wichtiges offenes Problem, ob diese Implikation umgekehrt werden kann: Bedeutet W [1] ≠ FPT die exponentielle Zeithypothese? Es gibt eine Hierarchie von parametrierten Komplexitätsklassen aufgerufen , um die M-Hierarchie , die verschachtelt die W-Hierarchie in dem Sinne , daß für alle i , M [ i ] ⊆ W [ i ] ⊆ M [ i + 1] ; Beispielsweise ist das Problem, eine Scheitelpunktabdeckung der Größe k log n in einem n- Vertex-Graphen mit dem Parameter k zu finden, für M [1] vollständig. Die exponentielle Zeithypothese entspricht der Aussage, dass M [1] ≠ FPT ist , und die Frage, ob M [ i ] = W [ i ] für i  > 1 ist, ist ebenfalls offen.

Es ist auch möglich, Implikationen in die andere Richtung zu beweisen, vom Versagen einer Variation der starken exponentiellen Zeithypothese bis zur Trennung von Komplexitätsklassen. Wie Williams (2010) zeigt, ist NEXPTIME keine Teilmenge von P / Poly , wenn es einen Algorithmus A gibt , der die Erfüllbarkeit der Booleschen Schaltung in der Zeit 2 n / ƒ ( n ) für eine superpolynomiell wachsende Funktion ƒ löst . Williams zeigt, dass, wenn Algorithmus A existiert und eine Familie von Schaltungen existiert, die NEXPTIME in P / Poly simulieren , Algorithmus A mit den Schaltungen zusammengesetzt werden könnte, um NEXPTIME-Probleme nicht deterministisch in einer kürzeren Zeitspanne zu simulieren, was den Zeithierarchiesatz verletzt . Die Existenz des Algorithmus A beweist daher die Nichtexistenz der Schaltungsfamilie und die Trennung dieser beiden Komplexitätsklassen.

Siehe auch

Anmerkungen

Verweise

  • Calabro, Chris; Impagliazzo, Russel ; Paturi, Ramamohan (2009), "Die Komplexität der Erfüllbarkeit kleiner Schaltungen", Parametrisierte und genaue Berechnung, 4. Internationaler Workshop, IWPEC 2009, Kopenhagen, Dänemark, 10.-11. September 2009, Revised Selected Papers , S. 75–85 .
  • Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), "Starke rechnerische Untergrenzen durch parametrisierte Komplexität", Journal of Computer and System Sciences , 72 (8): 1346–1367, doi : 10.1016 / j.jcss.2006.04.007 .
  • Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015), Parametrisierte Algorithmen , Springer, p. 555, ISBN   978-3-319-21274-6
  • Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał (2013), "Bekannte Algorithmen für EDGE CLIQUE COVER sind wahrscheinlich optimal", Proc. 24. ACM-SIAM-Symposium über diskrete Algorithmen (SODA 2013) , arXiv : 1203.1754 , Bibcode : 2012arXiv1203.1754C , archiviert vom Original am 16.04.2013 .
  • Dantsin, Evgeny; Wolpert, Alexander (2010), "Über mäßig exponentielle Zeit für SAT", Theorie und Anwendungen von Zufriedenheitstests - SAT 2010 , Lecture Notes in Computer Science, 6175 , Springer-Verlag, S. 313–325, doi : 10.1007 / 978- 3-642-14186-7_27 , ISBN   978-3-642-14185-0 .
  • Feige, Uriel ; Kilian, Joe (1997), "Über begrenzten versus polynomiellen Nichtdeterminismus", Chicago Journal of Theoretical Computer Science , 1 : 1–20, doi : 10.4086 / cjtcs.1997.001 .
  • Flum, Jörg; Grohe, Martin (2006), "16. Subexponentielle Traktabilität fester Parameter", Parametrisierte Komplexitätstheorie , EATCS-Texte in Theoretischer Informatik, Springer-Verlag, S. 417–451, ISBN   978-3-540-29952-3 .
  • Impagliazzo, Russell ; Paturi, Ramamohan (1999), "The Complexity of k-SAT", Proc. 14. IEEE Conf. on Computational Complexity , S. 237–240, doi : 10.1109 / CCC.1999.766282 , ISBN   978-0-7695-0075-1 .
  • Impagliazzo, Russell ; Paturi, Ramamohan; Zane, Francis (2001), "Welche Probleme haben eine stark exponentielle Komplexität?", Journal of Computer and System Sciences , 63 (4): 512–530, CiteSeerX   10.1.1.66.3717 , doi : 10.1006 / jcss.2001.1774 .
  • Karpinski, Marek ; Schudy, Warren (2010), "Schnellere Algorithmen für Feedback-Arc-Set-Turnier, Kemeny-Rangaggregation und Zwischen-Turnier", Proc. ISAAC 2010, Teil I , Lecture Notes in Computer Science, 6506 : 3–14, arXiv : 1006.4396 , doi : 10.1007 / 978-3-642-17517-6_3 , ISBN   978-3-642-17516-9 .
  • Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket (2011), "Bekannte Algorithmen auf Graphen mit begrenzter Baumbreite sind wahrscheinlich optimal", Proc. 22. ACM / SIAM-Symposium über diskrete Algorithmen (SODA 2011) (PDF) , S. 777–789, arXiv : 1007.5450 , Bibcode : 2010arXiv1007.5450L , archiviert vom Original (PDF) am 18.10.2012 , abgerufen 2011-05 -19 .
  • Pătraşcu, Mihai ; Williams, Ryan (2010), "Über die Möglichkeit schnellerer SAT-Algorithmen", Proc. 21. ACM / SIAM-Symposium über diskrete Algorithmen (SODA 2010) (PDF) , S. 1065–1075 .
  • Williams, Ryan (2010), "Die Verbesserung der erschöpfenden Suche impliziert superpolynomielle Untergrenzen", Proc. 42. ACM-Symposium zur Theorie des Rechnens (STOC 2010) , New York, NY, USA: ACM, S. 231–240, CiteSeerX   10.1.1.216.1299 , doi : 10.1145 / 1806689.1806723 , ISBN   9781450300506 .
  • Woeginger, Gerhard (2003), "Genaue Algorithmen für NP-harte Probleme: Eine Umfrage", Kombinatorische Optimierung - Eureka, You Shrink! (PDF) , Lecture Notes in Computer Science, 2570 , Springer-Verlag, S. 185–207, CiteSeerX   10.1.1.168.5383 , doi : 10.1007 / 3-540-36478-1_17 , ISBN   978-3-540-00580-3 .