FPT vs W [P] - Parametrisierte Komplexität

In parametrisierter Komplexität ist ≤ W [ 2 ] ≤ … ≤ W [ P ] . Es wird vermutet, dass jeder der Containments richtig ist.$\mathsf{FPT} \subseteq \mathsf{W}[1]$ $\subseteq \mathsf{W}[2]$ $\subseteq \ldots \subseteq \mathsf{W}[P]$

Wenn dann ist P = W [ P ] .$\mathsf{FPT}=\mathsf{W}[P]$$\mathsf{P}=\mathsf{W}[P]$

Aber folgt daraus?

• Wenn dann ist F P T = W [ P ] ? oder$\mathsf{FPT}=\mathsf{W}[1]$$\mathsf{FPT}=\mathsf{W}[P]$
• Wenn (für einige t), dann ist F P T = W [ P ] ?$\mathsf{W}[t-1]=\mathsf{W}[t]$$\mathsf{FPT}=\mathsf{W}[P]$

Diese Frage ist schwierig, da die Antwort (soweit ich weiß) immer noch "Weiß nicht" lautet.

Um dem etwas Gewicht zu verleihen, geben Flum & Grohe [1] als offene Probleme an (S. 164):

• $\mathrm{W}$$\mathrm{FPT} \neq \mathrm{W[P]}$
• $t \geq 1$$\mathrm{W}[t] = \mathrm{W}[t + 1]$$\mathrm{W}[t] = \mathrm{W}[t + 2]$

In der jüngsten Monographie von Downey und Fellow [2] heißt es außerdem (S. 521):

$\mathrm{W}$$\mathrm{W}[1] \neq \mathrm{W}[2]$

$\mathrm{W}$

Dem gehen auch voraus:

$t$

$$\mathrm{FPT} \neq \mathrm{W}[t]$$

$\mathrm{FPT} = \mathrm{W}[t-1]$

Verweise:

1. J. Flum und M. Grohe, "Parametrized Complexity Theory", Springer, 2006.
2. R. Downey und M. Fellows, "Grundlagen der parametrisierten Komplexitätstheorie", Springer, 2014.