Parametrisierte Komplexität - Parameterized complexity

In der Informatik ist parametrisierte Komplexität ein Zweig der Computational Complexity Theory , der sich auf die Klassifizierung von Rechenproblemen nach ihrer inhärenten Schwierigkeit in Bezug auf mehrere Parameter der Eingabe oder Ausgabe konzentriert. Die Komplexität eines Problems wird dann als Funktion dieser Parameter gemessen . Dies ermöglicht die Klassifizierung von NP-schweren Problemen auf einer feineren Skala als in der klassischen Umgebung, bei der die Komplexität eines Problems nur als Funktion der Anzahl der Bits in der Eingabe gemessen wird. Die erste systematische Arbeit zur parametrisierten Komplexität wurde von Downey & Fellows (1999) durchgeführt .

Unter der Annahme P ≠ NP gibt es viele natürliche Probleme, die eine superpolynomielle Laufzeit erfordern , wenn die Komplexität nur in Bezug auf die Eingabegröße gemessen wird, die jedoch in einer Zeit berechenbar sind, die in der Eingabegröße polynomiell und in a . exponentiell oder schlimmer ist Parameter k . Wenn also k auf einen kleinen Wert festgelegt ist und das Wachstum der Funktion über k relativ klein ist, können solche Probleme trotz ihrer traditionellen Klassifizierung als "unbeherrschbar" immer noch als "behandelbar" betrachtet werden.

Die Existenz effizienter, exakter und deterministischer Lösungsalgorithmen für NP-vollständige oder anderweitig NP-schwere Probleme wird als unwahrscheinlich erachtet, wenn die Eingabeparameter nicht festgelegt sind; alle bekannten Lösungsalgorithmen für diese Probleme erfordern eine exponentielle (oder zumindest superpolynomielle) Zeit in Bezug auf die Gesamtgröße der Eingabe. Einige Probleme können jedoch durch Algorithmen gelöst werden, die nur in der Größe eines festen Parameters exponentiell sind, während die Größe der Eingabe polynomiell ist. Ein solcher Algorithmus wird als lenkbarer (fpt-)Algorithmus mit festen Parametern bezeichnet , da das Problem für kleine Werte des festen Parameters effizient gelöst werden kann.

Probleme, bei denen ein Parameter k festgelegt ist, werden parametrisierte Probleme genannt. Ein parametrisierte Problem , dass für eine solche FPT-Algorithmus ermöglicht wird gesagt , eine sein fester Parameter lenkbar Problem und gehört zur Klasse FPT , und der frühe Name der Theorie der parametrisierte Komplexität wurde fest Parameter Lenkbarkeit .

Viele Probleme haben die folgende Form: ein Objekt gegeben x und eine nicht negative ganze Zahl k , ist x hat eine Eigenschaft, der davon abhängt k ? Für das Problem der Scheitelpunktüberdeckung kann der Parameter beispielsweise die Anzahl der Scheitelpunkte in der Überdeckung sein. In vielen Anwendungen, beispielsweise bei der Modellierung der Fehlerkorrektur, kann man davon ausgehen, dass der Parameter im Vergleich zur Gesamteingabegröße "klein" ist. Dann ist es schwierig, einen Algorithmus zu finden, der nur in k und nicht in der Eingabegröße exponentiell ist .

Auf diese Weise kann parametrisierte Komplexität als zweidimensionale Komplexitätstheorie betrachtet werden. Dieses Konzept ist wie folgt formalisiert:

Ein parametrisiertes Problem ist eine Sprache mit einem endlichen Alphabet. Die zweite Komponente wird als Parameter des Problems bezeichnet.${\displaystyle L\subseteq\Sigma^{*}\times\mathbb{N}}$${\displaystyle \Sigma}$

Ein parametrisiertes Problem L ist mit festen Parametern behandelbar, wenn die Frage " ?" kann in der Laufzeit entschieden werden , wobei f eine beliebige Funktion ist, die nur von k abhängt . Die entsprechende Komplexitätsklasse heißt FPT .${\displaystyle (x,k)\in L}$${\displaystyle f(k)\cdot |x|^{O(1)}}$

Zum Beispiel gibt es einen Algorithmus, der das Problem der Scheitelpunktüberdeckung zeitlich löst , wobei n die Anzahl der Scheitelpunkte und k die Größe der Scheitelpunktüberdeckung ist. Dies bedeutet, dass die Scheitelpunktüberdeckung mit der Größe der Lösung als Parameter mit festen Parametern steuerbar ist. ${\displaystyle O(kn+1,274^{k})}$

Komplexitätsklassen

FPT

FPT enthält die lenkbaren Probleme mit festen Parametern , die für eine berechenbare Funktion f rechtzeitig gelöst werden können . Typischerweise wird diese Funktion als einfach exponentiell betrachtet, wie z. B. aber die Definition lässt Funktionen zu, die noch schneller wachsen. Dies ist für einen großen Teil der Frühgeschichte dieser Klasse von wesentlicher Bedeutung. Der entscheidende Teil der Definition besteht darin, Funktionen des Formulars auszuschließen , wie z . Die Klasse FPL (fixed parameter linear) ist die Klasse von Problemen, die für eine berechenbare Funktion f zeitlich lösbar sind . FPL ist somit eine Unterklasse von FPT. ${\displaystyle f(k)\cdot {|x|}^{O(1)}}$${\displaystyle 2^{O(k)}}$${\displaystyle f(n,k)}$${\displaystyle n^{k}}$${\displaystyle f(k)\cdot |x|}$

Ein Beispiel ist das Erfüllbarkeitsproblem , parametrisiert durch die Anzahl der Variablen. Eine gegebene Formel der Größe m mit k Variablen kann durch Brute Force in der Zeit überprüft werden . Eine Knotenüberdeckung der Größe k in einem Graphen der Ordnung n in der Zeit gefunden werden , so dass dieses Problem auch in FPT ist. ${\displaystyle O(2^{k}m)}$${\displaystyle O(2^{k}n)}$

Ein Beispiel für ein Problem, von dem angenommen wird, dass es in FPT nicht auftritt, ist die Graphfärbung , die durch die Anzahl der Farben parametrisiert wird. Es ist bekannt, dass 3-Färbung NP-hart ist , und ein Algorithmus für Graph k- Färbung in der Zeit für würde in polynomieller Zeit in der Größe der Eingabe laufen. Wenn also die durch die Anzahl der Farben parametrisierte Graphenfärbung in FPT wäre, dann gilt P = NP . ${\displaystyle f(k)n^{O(1)}}$${\displaystyle k=3}$

Es gibt eine Reihe alternativer Definitionen von FPT. Beispielsweise kann die Laufzeitanforderung durch ersetzt werden . Ein parametrisiertes Problem liegt auch in FPT vor, wenn es einen sogenannten Kernel hat. Kernelization ist eine Vorverarbeitungstechnik, die die ursprüngliche Instanz auf ihren "harten Kernel" reduziert, eine möglicherweise viel kleinere Instanz, die der ursprünglichen Instanz entspricht, aber eine Größe hat, die durch eine Funktion im Parameter begrenzt ist. ${\displaystyle f(k)+|x|^{O(1)}}$

FPT wird unter einer parametrisierten Reduktion namens fpt-reduction geschlossen , die gleichzeitig die Instanzgröße und den Parameter beibehält .

Offensichtlich enthält FPT alle in Polynomialzeit berechenbaren Probleme. Darüber hinaus enthält es alle Optimierungsprobleme in NP, die ein effizientes Polynomial-Time-Approximation-Schema (EPTAS) ermöglichen .

W- Hierarchie

Die W- Hierarchie ist eine Sammlung von Rechenkomplexitätsklassen. Ein parametrisiertes Problem liegt in der Klasse W [ i ], wenn jede Instanz (in fpt-Zeit) in eine kombinatorische Schaltung umgewandelt werden kann, die höchstens Schuss i hat , so dass genau dann, wenn es eine befriedigende Zuweisung zu den Eingängen gibt, die weist 1 genau k Eingängen zu. Der Schuss ist die größte Anzahl logischer Einheiten mit unbegrenztem Auffächern auf einem beliebigen Pfad von einem Eingang zum Ausgang. Die Gesamtzahl der logischen Einheiten auf den Pfaden (als Tiefe bezeichnet) muss durch eine Konstante begrenzt werden, die für alle Instanzen des Problems gilt. ${\displaystyle (x,k)}$${\displaystyle (x,k)\in L}$

Beachten Sie das und für alle . Auch die Klassen in der W- Hierarchie sind unter fpt-Reduktion geschlossen. ${\displaystyle {\mathsf {FPT}}=W[0]}$${\displaystyle W[i]\subseteq W[j]}$${\displaystyle i\leq j}$

Viele natürliche Rechenprobleme besetzen die unteren Ebenen W [1] und W [2].

W [1]

Beispiele für W [1]-vollständige Probleme sind

• Entscheiden, ob ein gegebener Graph eine Clique der Größe k . enthält
• Entscheiden, ob ein gegebener Graph eine unabhängige Menge der Größe k . enthält
• Entscheidung, ob eine gegebene nichtdeterministische Single-Tape-Turingmaschine innerhalb von k Schritten akzeptiert ("Short Turing Machine Acceptance"-Problem). Dies gilt auch für nichtdeterministische Turing-Maschinen mit f ( k )-Bändern und sogar f ( k ) von f ( k )-dimensionalen Bändern, aber selbst mit dieser Erweiterung ist die Beschränkung auf die f ( k )-Bandalphabetgröße mit festen Parametern handhabbar. Entscheidend ist, dass die Verzweigung der Turingmaschine bei jedem Schritt von n , der Größe der Eingabe , abhängen darf . Auf diese Weise kann die Turing-Maschine n ^{O( k )} Berechnungspfade erkunden .

W [2]

Beispiele für W [2]-vollständige Probleme sind

• Entscheiden, ob ein gegebener Graph eine dominierende Menge der Größe k . enthält
• Entscheiden, ob eine gegebene nichtdeterministische Multi-Tape-Turing-Maschine innerhalb von k Schritten akzeptiert ("kurze Multi-Tape-Turing-Maschinen-Akzeptanz"-Problem). Entscheidend ist, dass die Verzweigung von n abhängen darf (wie bei der W[1]-Variante), ebenso wie die Anzahl der Bänder. Eine alternative W [2]-vollständige Formulierung erlaubt nur Single-Tape-Turing-Maschinen, aber die Alphabetgröße kann von n abhängen .

W [ t ]

${\displaystyle W[t]}$kann unter Verwendung der Familie der Weighted Weft- t -Depth- d SAT-Probleme definiert werden für : ist die Klasse parametrisierter Probleme, die fpt-reduziert auf dieses Problem, und . ${\displaystyle d\geq t}$${\displaystyle W[t,d]}$${\displaystyle W[t]=\bigcup _{d\geq t}W[t,d]}$

Hier ist Weighted Weft- t -Depth- d SAT das folgende Problem:

• Eingabe: Eine Boolesche Formel mit einer Tiefe von höchstens d und einem Schuss von höchstens t und einer Zahl k . Die Tiefe ist die maximale Anzahl von Toren auf einem beliebigen Pfad von der Wurzel zu einem Blatt, und der Schuss ist die maximale Anzahl von Toren des Auffächerns von mindestens drei auf jedem Pfad von der Wurzel zu einem Blatt.
• Frage: Hat die Formel eine befriedigende Zuweisung des Hamming-Gewichts genau k ?

Es kann gezeigt werden, dass für das Problem Weighted t -Normalize SAT für Unterfpt-Reduktionen vollständig ist . Hier ist Weighted t -Normalize SAT das folgende Problem: ${\displaystyle t\geq 2}$${\displaystyle W[t]}$

• Eingabe: Eine Boolesche Formel der Tiefe höchstens t mit einem UND-Gatter darüber und einer Zahl k .
• Frage: Hat die Formel eine befriedigende Zuweisung des Hamming-Gewichts genau k ?

W [ P ]

W [ P ] ist die Klasse von Problemen, die von einer nichtdeterministischen Turingmaschine entschieden werden können, die bei der Berechnung höchstens nichtdeterministische Entscheidungen trifft (eine k- beschränkte Turingmaschine). Flum & Grohe (2006)${\displaystyle h(k)\cdot {|x|}^{O(1)}}$${\displaystyle O(f(k)\cdot\log n)}$${\displaystyle (x,k)}$

Es ist bekannt, dass FPT in W[P] enthalten ist, und es wird angenommen, dass die Inklusion streng ist. Die Lösung dieses Problems würde jedoch eine Lösung des P-gegen-NP- Problems implizieren .

Andere Verbindungen zur nicht parametrisierten Rechenkomplexität sind, dass FPT gleich W [ P ] ist, wenn und nur wenn die Erfüllbarkeit der Schaltung in der Zeit entschieden werden kann , oder wenn und nur wenn es eine berechenbare, nicht abnehmende, unbeschränkte Funktion f gibt, so dass alle Sprachen von einem nichtdeterministischen Polynom erkannt werden -Zeit-Turingmaschine mit nichtdeterministischen Entscheidungen sind in  P . ${\displaystyle \exp(o(n))m^{O(1)}}$${\displaystyle f(n)\log n}$

W [ P ] kann man sich grob als die Klasse von Problemen vorstellen, bei denen wir eine Menge S von n Elementen haben und eine Teilmenge der Größe k finden wollen, so dass eine bestimmte Eigenschaft gilt. Wir können eine Auswahl als Liste von k ganzen Zahlen codieren , die im Binärformat gespeichert sind. Da die höchste dieser Zahlen n sein kann , werden Bits für jede Zahl benötigt. Daher werden Gesamtbits benötigt, um eine Auswahl zu codieren. Daher können wir eine Teilmenge mit nichtdeterministischen Auswahlmöglichkeiten auswählen . ${\displaystyle T\subset S}$${\displaystyle \lceil\log_{2}n\rceil}$${\displaystyle k\cdot \lceil\log_{2}n\rceil}$${\displaystyle T\subset S}$${\displaystyle O(k\cdot\log n)}$

XP

XP ist die Klasse parametrisierter Probleme, die für eine berechenbare Funktion f rechtzeitig gelöst werden können . Diese Probleme werden scheibenweises Polynom genannt, in dem Sinne, dass jede "Scheibe" von festem k einen polynomischen Algorithmus hat, wenn auch möglicherweise mit einem anderen Exponenten für jedes k. Vergleichen Sie dies mit FPT, das lediglich einen anderen konstanten Vorfaktor für jeden Wert von k zulässt. XP enthält FPT, und es ist bekannt, dass diese Eindämmung durch Diagonalisierung streng ist. ${\displaystyle n^{f(k)}}$

para-NP

para-NP ist die Klasse parametrisierter Probleme, die durch einen nichtdeterministischen Algorithmus zeitlich für eine berechenbare Funktion f gelöst werden können . Es ist bekannt, dass genau dann, wenn . ${\displaystyle f(k)\cdot |x|^{O(1)}}$${\displaystyle {\textsf {FPT}}={\textsf {para-NP}}}$${\displaystyle {\textsf {P}}={\textsf {NP}}}$

Ein Problem ist para-NP-schwer, wenn es bereits für einen konstanten Wert des Parameters -schwer ist . Das heißt, es gibt eine "Scheibe" von festem k , die -hart ist. Ein parametrisiertes Problem, das -hard ist, kann nicht zur Klasse gehören , es sei denn, . Ein klassisches Beispiel für ein -hart parametrisiertes Problem ist die Graphfärbung , parametrisiert durch die Anzahl k der Farben, für die bereits -hart ist (siehe Graphfärbung#Computational Complexity ). ${\displaystyle {\textsf {NP}}}$${\displaystyle {\textsf {NP}}}$${\displaystyle {\textsf {para-NP}}}$${\displaystyle {\textsf {XP}}}$${\displaystyle {\textsf {P}}={\textsf {NP}}}$${\displaystyle {\textsf {para-NP}}}$${\displaystyle {\textsf {NP}}}$${\displaystyle k=3}$

Eine Hierarchie

Die A-Hierarchie ist eine Sammlung von Rechenkomplexitätsklassen ähnlich der W-Hierarchie. Während jedoch die W-Hierarchie eine in NP enthaltene Hierarchie ist, ahmt die A-Hierarchie die Polynomialzeit-Hierarchie der klassischen Komplexität genauer nach. Es ist bekannt, dass A[1] = W[1] gilt.

Anmerkungen

Verweise

• Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2006). Verbesserte parametrisierte Obergrenzen für Vertex Cover . MFCS 2006 . Skript zur Vorlesung Informatik. 4162 . S. 238–249. CiteSeerX  10.1.1.432.831 . doi : 10.1007/11821069_21 . ISBN 978-3-540-37791-7.
• Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015). Parametrisierte Algorithmen . Springer. s. 555. ISBN 978-3-319-21274-6.
• Downey, Rod G .; Fellows, Michael R. (1999). Parametrisierte Komplexität . Springer. ISBN 978-0-387-94883-6.
• Flum, Jörg ; Grohe, Martin (2006). Parametrisierte Komplexitätstheorie . Springer. ISBN 978-3-540-29952-3.
• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019). Kernelisierung: Theorie der parametrisierten Vorverarbeitung . Cambridge University Press. s. 528. doi : 10.1017/9781107415157 . ISBN 978-1107057760.
• Niedermeier, Rolf (2006). Einladung zu Festparameteralgorithmen . Oxford University Press. ISBN 978-0-19-856607-6. Archiviert vom Original am 24.09.2008.
• Grohe, Martin (1999). „Beschreibende und parametrisierte Komplexität“. Logik der Informatik . Skript zur Vorlesung Informatik. 1683 . Springer Berlin-Heidelberg. S. 14–31. CiteSeerX  10.1.1.25.9250 . doi : 10.1007/3-540-48168-0_3 . ISBN 978-3-540-66536-6.
• Das Computerjournal. Band 51, Nummern 1 und 3 (2008). Das Computerjournal . Special Double Issue on Parameterized Complexity mit 15 Übersichtsartikeln, Buchrezension und einem Vorwort der Gastherausgeber R. Downey, M. Fellows und M. Langston.

Externe Links

• Wiki zu parametrisierter Komplexität
• Kompendium parametrisierter Probleme