Jaka jest motywacja definicji ciągliwości parametrów stałych?

FPT zawiera ustalone, możliwe do rozwiązania problemy, które można rozwiązać w czasie dla niektórych funkcji obliczalnych . Zwykle funkcja ta jest traktowana jako pojedynczy wykładniczy, taki jak ale definicja dopuszcza funkcje, które rosną jeszcze szybciej. Jest to niezbędne dla dużej części wczesnej historii tej klasy. Zasadniczą częścią definicji jest wykluczenie funkcji formy , takich jak $f(k)\cdot|x|^{O(1)}$ $f$ $2^{O(k)}$ $f(n,k)$ $n^k$ .

Pytanie : Jaka jest motywacja tej definicji?

Zastanawiające jest dla mnie to, że jeśli jest ustalone (zgodnie z „ustaloną podatnością parametrów”), to jest wielomianem w . Więc dlaczego jest kluczowa, aby wykluczyć ? $k$ $n^k$ $n$ $n^k$

cc.complexity-theory fixed-parameter-tractable Douglas S. Kamienie
źródło

n^{k}

$n^k$

n \approx 1000000

$n ≈ 1000000$

k \approx 30

$k ≈ 30$

n^{k}

$n^k$

Zgadza się. Oczywiście istnieje hierarchia problemów ze stałymi parametrami, a FPT znajduje się na dole. n ^ k jest na górze. Mówiąc bardziej ogólnie, celem jest próba oddzielenia wpływu parametru i wpływu

, a zatem dwóch oddzielnych części czasu przebiegu.

n

$n$

Suresh Venkat

@JukkaSuomela: Myślę, że twój komentarz może być odpowiedzią.

Suresh Venkat

Odpowiedzi:

$n$ $k$

$n$ $2^k n^2$ $k^2 n^k$ $k$ $n$ wzrastający. Ta intuicja jest wspierana zarówno w praktyce, jak i w teorii; tzn. problemy FPT są zwykle bardziej praktyczne w praktyce niż arbitralne problemy XP, a także można uzyskać ładny teoretyczny obraz struktury XP, zaczynając od FPT na dole i konstruując hierarchie innych podklas XP (takich jak Hierarchia W.) powyżej.

Timothy Chow
źródło