Kernel in parametrisierter Komplexität

7

Kann mir jemand erklären, was (Problem-) Kernel sind und wozu sie dienen? Meine Folien sagen:

Der Kern eines parametrisierten Problems L ist eine Transformation (x,k)↦(x′,k′) so dass:

  • (x,k)∈L⇔(x′,k′)∈L
  • |x′|≤f(k) für eine Funktion f
  • k′≤g(k) für eine Funktion g
  • Die Transformation muss in Polynomzeit berechnet werden.

Meine Fragen sind:

  • Wie hängt dies mit einem Problem zusammen, bei dem feste Parameter nachvollziehbar sind?
  • Was macht Kernel nützlich?
  • Woher kommt diese Definition?

Das Beispiel auf meinen Folien ist für die Scheitelpunktabdeckung, aber ich verstehe es nicht wirklich, weil die Folien etwas kurz sind.

parameterized-complexity algorithm-design Peter W.
quelle
Hier scheint es sich um eine Familie von Algorithmen zu handeln, aber ich kann nicht erraten, welche. Könnten Sie einen Kontext geben.
Babou
1
Dies ist ein eher standardmäßiges (wenn nicht grundlegendes) Konzept in der Komplexitätstheorie. Dies sind Dinge, die Ihr Lehrer Ihnen hätte sagen sollen, aber es gibt auch viel Material im Internet, ganz zu schweigen von Büchern. Wo hast du gesucht Haben Sie sogar eine einfache Suche durchgeführt? (cc @babou)
Raphael
1
@Raphael Wie kommt es, dass eine Frage zu NP 80 Upvotes erhält und Sie denken, dass die Komplexität der Kernelisierung für diese Site zu Standard (wenn nicht grundlegend) ist? Wenn der Lehrer dies hätte sagen sollen, können wir davon ausgehen, dass der Lehrer auch P, NP, NP-Complete und NP-Hard erklärt.
Pål GD

Antworten:

8

Intuitiv ist ein Kernelisierungsalgorithmus ein Algorithmus, der in Polynomzeit eine bestimmte Instanz vorverarbeitet und eine Instanz ausgibt, deren Größe im Parameter begrenzt ist. Das Ziel der Kernelisierung ist (mindestens) zweifach. Wir erhalten nachweisbare Leistungsgarantien, dh wir können Obergrenzen für die Ausgabeinstanz nachweisen, die sowohl beim Entwurf von Algorithmen als auch als Komplexitätsmaß Anwendung findet.

Kernel-Diagramm

Formal gesehen ist ein Kernelisierungsalgorithmus (oft als Kernel bezeichnet) ein Algorithmus für ein Problem, das bei einer Eingabe auftritt (G,k)gibt eine äquivalente Instanz aus (G′,k′) mit max{|G′|,k′}≤f(k) für eine Funktion f. Darüber hinaus muss der Algorithmus in Polynomzeit ausgeführt werden.

Das folgende Ergebnis zeigt, dass die Leistung von Kerneln sozusagen der Leistung der Traktierbarkeit fester Parameter ( PDF ) entspricht.

Satz (Folklore). Ein Problem ist ein fester Parameter, der genau dann nachvollziehbar ist, wenn er einen Kernel zulässt und entscheidbar ist.

Obwohl der Begriff des Kernels mit der Traktierbarkeit fester Parameter übereinstimmt, gibt es eine stärkere Version der Kernelisierung, bei der wir die Funktion fordern f oben ein Polynom sein.

Wenn Sie die ursprünglichen Definitionen sehen möchten, empfehle ich Ihnen, das Buch von Downey und Fellows über parametrisierte Komplexität in die Hand zu nehmen oder mit Niedermeiers oben erwähnter Habilitationsarbeit zu beginnen. Es gibt auch einen Wikipedia-Artikel über Kernelisierung .

Pål GD
quelle
Vielen Dank, das macht die Dinge klarer! Grundsätzlich besteht das Ziel der Kernelisierung darin, eine kleinere Instanz des Problems zu erhalten, die nur auf k beschränkt ist, sodass Sie das Problem auf der kleineren Instanz in O (f (k)) lösen und die kombinierte Laufzeit (= Berechnung) erhalten können der Kernel + das Lösen der neuen Instanz) von etwas wie O (f (k) + p (n)), was gut für kleine k ist?
Peter W
Die Notiz "(Folklore)" deutet darauf hin, dass wir keinen formalen Beweis haben. Ich scheine mich jedoch an einen zu erinnern. Wie sollen wir interpretieren, was Sie schreiben?
Raphael
1
@Raphael, die früheste Zuschreibung (glaube ich) ist Rolf Niedermeiers Habilitationsschrift (2002) , die 2006 als Monographie veröffentlicht wurde Theoretisch ist es allgemein üblich geworden, dass „jedes nachvollziehbare Problem mit festen Parametern kernelisierbar ist“. Daher die traditionellere Zuschreibung zur Folklore.
Luke Mathieson
Das ist irgendwie lustig, Rolf Niedermeier ist der Professor, der mich bald testen wird.
Peter W
@LukeMathieson Lemma 4.8 (S. 31) der parametrisierten Komplexität: Ein Rahmen für die systematische Auseinandersetzung mit der Unlösbarkeit von Berechnungen, Downey, Fellows and Stege, 1997, lautet: "Ein parametrisiertes ProblemList in FPT genau dann, wenn es kernelierbar ist ". ( PDF )
Pål GD