Exponentialzeithypothese

Im Computerkomplexitätstheorie, das Exponentialzeithypothese ist ein unbewiesenes Berechnungshärte Annahme das wurde von formuliert Impagliazzo & Paturi (1999). Die Hypothese besagt, dass das 3-sa kann nicht gelöst werden suberponentielle Zeit in dem schlimmsten Fall. Die Exponentialzeithypothese würde das implizieren, wenn dies wahr ist P ≠ np, aber es ist eine stärkere Aussage. Es kann verwendet werden, um zu zeigen, dass viele Rechenprobleme in der Komplexität gleichwertig sind, in dem Sinne, dass sie alle, wenn einer von ihnen einen Zeitalgorithmus für subtexponentielle Zeit hat, alle dies tun.

Definition

k-Sat ist das Problem des Testens, ob a Boolescher Ausdruck, in Konjunktive normale Form mit höchstens k Variablen pro Klausel können durch eine Zuweisung von booleschen Werten zu seinen Variablen zutreffend gemacht werden. Für jede ganze Zahl k ≥ 3 definieren Sie eine reelle Zahl sk zu sein Infimum der realen Zahlen δ für die k-Sat kann in der Zeit o algorithmisch gelöst werden (2δn), wo n ist die Anzahl der Variablen in der gegebenen k-Sat -Instanz. Es hält das s3≤s4≤ ..., da die Schwierigkeit beim Wachstum nicht abnimmt k.

Das Exponentialzeithypothese ist der Vermutung das sk> 0 für jeden k ≥ 3 oder entsprechend das s3> 0.

Einige Quellen definieren die exponentielle Zeithypothese als etwas schwächere Aussage, dass 3-SAT in der Zeit 2 nicht gelöst werden kannÖ(n). Wenn es einen Algorithmus gab, um 3-sat in der Zeit 2 zu lösenÖ(n), dann s3 würde Null gleich. Es steht jedoch im Einklang mit dem aktuellen Wissen, dass es eine Folge von 3-SAT-Algorithmen mit jeweils Laufzeit O (2) geben könnteδin) für eine Folge von Zahlen δi Tendenz zu Null, aber wo die Beschreibungen dieser Algorithmen so schnell wachsen, dass ein einzelner Algorithmus nicht automatisch die am besten geeigneten auswählen und ausführen konnte.[1]

Weil die Zahlen s3, s4, ... Form a Monotonische Sequenz Das ist oben durch eins begrenzt, sie müssen zu einer Grenze konvergieren s∞. Das starke Exponentialzeithypothese (Seth) ist die Vermutung, die s∞= 1.[2]

Eine andere Variante ist die ungleichmäßige Exponentialzeithypothese, eine Stärkung der zweiten Formulierung der ETH, die davon ausgeht, dass es keine Familie von Algorithmen gibt Rat) das kann 3-sa-Zeit in der Zeit 2 lösenÖ(n).

Auswirkungen auf die Erfüllbarkeit

Es ist nicht möglich für sk gleich s∞ für jede endliche k: wie Impagliazzo, Paturi & Zane (2001) gezeigt, es gibt eine Konstante α so dass sk≤s∞(1 -α/k). Wenn die Exponentialzeithypothese wahr ist, muss es unendlich viele Werte von geben k für welche sk unterscheidet sich von sk+1.

Ein wichtiges Werkzeug in diesem Bereich ist die Sparsifikation Lemma von Impagliazzo, Paturi & Zane (2001)das zeigt das für jeden ε> 0, jeder k-CNF -Formel kann durch o (2) ersetzt werdenεn) einfacher k-CNF -Formeln, bei denen jede Variable nur eine konstante Anzahl von Male erscheint und daher die Anzahl der Klauseln linear ist. Die Sparsifikation Lemma wird nachgewiesen, indem wiederholt große Sätze von Klauseln gefunden werden, die in einer bestimmten Formel einen nicht leeren gemeinsamen Schnittpunkt haben und die Formel durch zwei einfachere Formeln ersetzen, von denen eines jeder dieser Klauseln ersetzt wird Hat die Kreuzung von jeder Klausel entfernt. Durch die Anwendung des Sparifizierungs -Lemma und die Verwendung neuer Variablen zum Aufteilen der Klauseln kann man dann einen Satz von O (2) erhaltenεn) 3-CNF-Formeln, jeweils eine lineare Anzahl von Variablen, so dass das Original k-CNF-Formel ist nur dann erfüllen, wenn mindestens eine dieser 3-CNF-Formeln erfüllt ist. Wenn 3-SAT in der subenexponentiellen Zeit gelöst werden könnte, könnte man diese Reduktion verwenden, um zu lösen k-Sat auch in der subenexponentiellen Zeit. Äquivalent, wenn sk> 0 für jeden k> 3 dann s3> 0 auch, und die Exponentialzeithypothese wäre wahr.[3][4]

Der begrenzende Wert s∞ der Reihenfolge der Zahlen sk ist höchstens gleich zu sCNF, wo sCNF ist das Infimum der Zahlen δ so dass die Erfüllbarkeit von Konjunktiv -Normalformformeln ohne Klausellängengrenzen in der Zeit O gelöst werden kann (2δn). Wenn die starke Exponentialzeithypothese wahr ist, gäbe es keinen Algorithmus für die allgemeine CNF Wahrheitsaufträge. Wenn jedoch die starke Exponentialzeithypothese fehlschlägt, wäre sie immer noch möglich sCNF eins gleich.[5]

Implikationen für andere Suchprobleme

Die exponentielle Zeithypothese impliziert, dass viele andere Probleme in der Komplexitätsklasse SNP Haben Sie keine Algorithmen, deren Laufzeit schneller ist als cn für einige Konstantec. Diese Probleme umfassen Graph k-Colorierbarkeit, finden Hamiltonsche Zyklen, Maximale Cliquen, Maximale unabhängige Sets, und Scheitelpunktabdeckung an n-Vertex -Diagramme. Wenn eines dieser Probleme einen subtexponentiellen Algorithmus aufweist, kann sich gezeigt, dass die Exponentialzeithypothese falsch ist.[3][4]

Wenn Cliquen oder unabhängige Mengen logarithmischer Größe in der Polynomzeit gefunden werden könnten, wäre die Exponentialzeithypothese falsch. Obwohl das Finden von Cliquen oder unabhängigen Sätzen solcher geringer Größe nicht np-vollständig ist, impliziert die exponentielle Zeithypothese, dass diese Probleme nicht polynomisch sind.[3][6] Allgemeiner impliziert die Exponentialzeithypothese, dass es nicht möglich ist, Cliquen oder unabhängige Größensätze zu finden k rechtzeitig no(k).[7] Die exponentielle Zeithypothese impliziert auch, dass es nicht möglich ist, die zu lösen k-SUMME Problem (gegeben n reelle Zahlen, finden Sie k von ihnen, die zu Null hinzufügen) rechtzeitig no(k). Die starke exponentielle Zeithypothese impliziert, dass es nicht möglich ist zu finden k-Vertex dominiert setzt schneller als rechtzeitig nk-o(1).[5]

Die Exponentialzeit -Hypothese impliziert auch, dass das (schnelle) -Reproblem gewichteter Rückkopplungsbogensatz kein parametrisierter Algorithmus mit der Laufzeit aufweist O*(2o(√Opt)), es hat einen parametrisierten Algorithmus mit Laufzeit O*(2O(√Opt)).[8]

Die starke exponentielle Zeithypothese führt zu engen Grenzen auf der Parametrisierte Komplexität von mehreren Grafikproblemen in Grafiken von begrenzt Baumbreite. Insbesondere, wenn die starke Exponentialzeithypothese wahr ist, dann ist die optimale Zeit, die unabhängige Sätze in Graphen der Baumbreite finden w ist (2 - o(1))wnO(1), die optimale Zeit für die dominierender Satz Das Problem ist (3 - o(1))wnO(1)die optimale Zeit für Maximaler Schnitt ist (2 - o(1))wnO(1)und die optimale Zeit für k-Coloring ist (k − o(1))wnO(1).[9] Äquivalent würde jede Verbesserung dieser Laufzeiten die starke Exponentialzeithypothese verfälschen.[10] Die Exponentialzeithypothese impliziert auch, dass jeder fixe Parameter-Traktable-Algorithmus für Rand Clique -Abdeckung haben müssen Doppelte Exponential Abhängigkeit vom Parameter.[11]

Auswirkungen der Kommunikationskomplexität

Im Drei-Parteien-Set Disjunktizität Problem in Kommunikationskomplexität, drei Teilmengen der ganzen Zahlen in einem Bereich [1,m] werden angegeben, und drei Kommunikationsparteien kennen jeweils zwei der drei Teilmengen. Das Ziel ist es, dass die Parteien auf einem gemeinsamen Kommunikationskanal als wenige Bits als nur wenige Bits ü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, wenn eine der drei Parteien a überträgt Bitvektor Beschreibung der Schnittstelle der beiden Sätze, die dieser Partei bekannt sind, wonach eine der beiden verbleibenden Parteien die Leere der Schnittstelle bestimmen kann. Wenn es jedoch ein Protokoll gibt, das das Problem mit O ((m) Kommunikation und 2Ö(m) Berechnung, es könnte zum Lösen in einen Algorithmus umgewandelt werden k-Sat in der Zeit o (1.74)n) für eine feste Konstante kVerstoß gegen die starke Exponentialzeithypothese. Daher impliziert die starke exponentielle Zeithypothese entweder, dass das triviale Protokoll für die Drei-Parteien-Setdisjunktheit optimal ist oder dass ein besseres Protokoll eine exponentielle Berechnung erfordert.[5]

Auswirkungen der strukturellen Komplexität

Wenn die Hypothese der exponentiellen Zeit wahr ist, hätte 3-SAT keinen Polynomzeitalgorithmus, und deshalb würde dies folgen P ≠ np. In diesem Fall konnte 3-SAT in diesem Fall nicht einmal eine haben Quasi-Polynomzeit Algorithmus, so dass NP keine Teilmenge von QP sein konnte. Wenn die Exponentialzeithypothese jedoch fehlschlägt, hätte sie keine Auswirkungen auf das P -Versus -NP -Problem. Es gibt NP-Complete-Probleme, für die die bekanntesten Laufzeiten die Form O (2) habennc) zum c<1, und wenn die bestmögliche Laufzeit für 3-SAT von dieser Form wäre, wäre P für NP ungleich (da 3-sa np-complete ist und diese Zeit nicht polynomisch ist), aber die Exponentialzeithypothese wäre FALSCH.

In der parametrisierten Komplexitätstheorie, da die Hypothese der exponentiellen Zeit impliziert, dass es keinen festen Parameter-Algorithmus für maximale Clique gibt, impliziert dies auch, dass dies impliziert W [1] ≠ fpt.[7] Es ist ein wichtiges offenes Problem in diesem Bereich, ob diese Implikation umgekehrt werden kann: tut W [1] ≠ fpt die Exponentialzeithypothese implizieren? Es gibt eine Hierarchie parametrisierter Komplexitätsklassen, die als M-hierarchie bezeichnet werden, die die W-hierarchie in dem Sinne verschachtelt, dass für alle i, M[i] ⊆ w [i] ⊆ m [i + 1]; Zum Beispiel das Problem, a zu finden Scheitelpunktabdeckung von Größe k Protokoll n in einem (n n-Vertex -Diagramm mit Parameter k ist vollständig für M [1]. Die Exponentialzeithypothese entspricht der Aussage, dass M [1] ≠ fpt, und die Frage, ob m [[i] = W [i] zum i> 1 ist auch offen.[1]

Es ist auch möglich, Auswirkungen in die andere Richtung zu beweisen, von dem Versagen einer Variation der starken Exponentialzeithypothese bis hin zu Trennungen von Komplexitätsklassen. Wie Williams (2010) zeigt, wenn es einen Algorithmus gibt A Das löst die Boolesche Schaltungszufriedenheit in Zeit 2n/ƒ (n) für einige superpolynomial wachsende Funktion ƒ, dann Nexptime ist keine Teilmenge von P/poly. Williams zeigt das, wenn Algorithmus A existiert und eine Familie von Schaltungen simulierte das Nexptime in P/Poly auch, dann Algorithmus A könnte mit den Schaltungen zusammengesetzt sein, um nexptime Probleme nicht in einer geringeren Zeit zu simulieren und gegen die zu verstoßen Zeithierarchie Theorem. Daher die Existenz des Algorithmus A beweist die Nichtdage der Familie der Schaltungen und die Trennung dieser beiden Komplexitätsklassen.

Siehe auch

Anmerkungen

  1. ^ a b Flum & Grohe (2006).
  2. ^ Calabro, Impagliazzo & Paturi (2009).
  3. ^ a b c Woeginger (2003).
  4. ^ a b Impagliazzo, Paturi & Zane (2001).
  5. ^ a b c Pătraşcu & Williams (2010).
  6. ^ Feige & Kilian (1997).
  7. ^ a b Chen et al. (2006).
  8. ^ Karpinski & Schudy (2010)
  9. ^ Cygan et al. (2015)
  10. ^ Lokshtanov, Marx & Saurabh (2011).
  11. ^ Cygan, Pilipczuk & Pilipczuk (2013).

Verweise

  • Calabro, Chris; Impagliazzo, Russel; PATURI, Ramamohan (2009), "Die Komplexität der Erfüllbarkeit kleiner Tiefenschaltungen", Parametrisierte und exakte Berechnung, 4. Internationaler Workshop, IWPEC 2009, Kopenhagen, Dänemark, 10. bis 11. September 2009, überarbeitete ausgewählte Arbeiten, S. 75–85.
  • Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, GE (2006), "Starke rechnerische Untergrenzen über 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 für diskrete Algorithmen (Soda 2013), Arxiv:1203.1754, Bibcode:2012ArXIV1203.1754c, archiviert von das Original Am 2013-04-16.
  • Dantsin, Evgeny; Wolpert, Alexander (2010), "über mäßig exponentielle Zeit für SAT", Theorie und Anwendungen von Erfriedigungstests - SAT 2010, Vorlesungsnotizen in Informatik, Vol. 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 Limited versus Polynom -Nichtdeterminismus", Chicago Journal of Theoretical Informatik, 1: 1–20, doi:10.4086/cjtcs.1997.001.
  • Flum, Jörg; Grohe, Martin (2006), "16. subexponentiale Fix-Parameter-Traktabilität", Parametrisierte Komplexitätstheorie, Eatcs Texte in theoretischer Informatik, Springer-Verlag, S. 417–451, ISBN 978-3-540-29952-3.
  • Impagliazzo, Russell; Paturi, Ramamohan (1999), "Die Komplexität von K-sa", Proc. 14. IEEE Conf. zur rechnerischen Komplexität, 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 stark exponentielle Komplexität?", Journal of Computer and System Sciences, 63 (4): 512–530, Citeseerx 10.1.1.66.3717, doi:10.1006/jcs.2001.1774.
  • Karpinski, Marek; Schudy, Warren (2010), "schnellere Algorithmen für das Feedback -Bogen -Set -Turnier, Kemeny -Rang -Aggregation und Zwischenheitsturnier", Proc. Isaac 2010, Teil I., Vorträge in Informatik, 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 in Graphen der begrenzten 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 von das Original (PDF) Am 2012-10-18, 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), "Verbesserung der umfassenden Suche impliziert superpolynomische Untergrenzen", ", Proc. 42. ACM -Symposium über die Computertheorie (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), "exakte Algorithmen für NP-HART-Probleme: eine Umfrage", Kombinatorische Optimierung - Eureka, du schrumpfen! (PDF), Vorlesungsnotizen in Informatik, Vol. 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.