Was ist die Motivation für die Definition der Traktierbarkeit fester Parameter?

FPT enthält die mit festen Parametern verfolgbaren Probleme, die in der Zeit für eine berechenbare Funktion gelöst werden können . Typischerweise wird diese Funktion als einzelnes Exponential 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ühen Geschichte dieser Klasse von wesentlicher Bedeutung. Der entscheidende Teil der Definition besteht darin, Funktionen der Form wie auszuschließen . $f(k)\cdot|x|^{O(1)}$ $f$ $2^{O(k)}$ $f(n,k)$ $n^k$

Frage : Was ist die Motivation hinter dieser Definition?

Was mich verwundert ist, dass wenn fest ist (gemäß "Traktabilität fester Parameter"), ein Polynom in . Warum ist es also wichtig, auszuschließen ? $k$ $n^k$ $n$ $n^k$

cc.complexity-theory fixed-parameter-tractable Douglas S. Stones
quelle

Weil aus theoretischer Sicht oft sowohl trivial als auch aus praktischer Sicht viel zu langsam ist. Ein Weg, es auszudrücken, ist, dass das FPT-Geschäft versucht, die rechnerische Komplexität von Problemen für die Werte von Parametern zu verstehen, die im Ballpark von und .

n^{k}

$n^k$

n \approx 1000000

$n ≈ 1000000$

k \approx 30

$k ≈ 30$

Jukka Suomela

Hmm ... also, wenn ich richtig verstehe, wenn wir in FPT lassen, werden wir am Ende eine Reihe von Entscheidungsproblemen trivial über Brute-Force-Algorithmen einbeziehen.

n^{k}

$n^k$

Douglas S. Stones

Das stimmt. Natürlich gibt es eine Hierarchie fester Parameterprobleme, und FPT befindet sich ganz unten. n ^ k ist oben. Allgemeiner besteht die Idee darin, den Einfluss des Parameters und den Einfluss von und damit die beiden getrennten Teile der Laufzeit zu trennen.

n

$n$

Suresh Venkat

@JukkaSuomela: Ich denke, dein Kommentar könnte eine Antwort sein.

Suresh Venkat

Antworten:

Wenn Sie nur verlangen, dass die Wachstumsrate ein Polynom in für festes , erhalten Sie die Definition der parametrisierten Komplexitätsklasse XP, die sicherlich von Interesse ist, sodass nichts falsch daran ist, sie zu berücksichtigen. $n$ $k$

Sie erhalten die Definition von FPT, wenn Sie die Bedingung weiter auferlegen, dass der Grad des Polynoms in zunehmendem Parameter fest bleibt . FPT stellt sich als besonders handhabbare Unterklasse von XP heraus, und intuitiv liegt der Grund darin, dass ein Ausdruck wie nicht so schnell explodiert wie ein Ausdruck wie , wenn und sind beide $n$ $2^k n^2$ $k^2 n^k$ $k$ $n$ zunehmend. Diese Intuition wird sowohl in der Praxis als auch in der Theorie unterstützt; Das heißt, FPT-Probleme sind in der Praxis in der Regel merklich leichter zu lösen als beliebige XP-Probleme, und man kann sich auch ein gutes theoretisches Bild über die Struktur von XP machen, indem man mit FPT unten beginnt und Hierarchien anderer XP-Unterklassen (wie z W Hierarchie) darüber.

Timothy Chow
quelle