Wystąpienie redukcji FPT, która nie jest redukcją czasu wielomianowego

W sparametryzowanej złożoności ludzie używają redukcji stałych parametrów (FPT), aby udowodnić twardość W [t]. Teoretycznie redukcja FPT nie jest redukcją czasu wielomianowego, ponieważ może działać wykładniczo w parametrze k. Ale w praktyce wszystkie redukcje FPT, które widziałem, są redukcjami czasu p, co oznacza, że ​​dowody twardości W [t] prawie zawsze implikują dowody kompletności NP.

Zastanawiam się, czy ktoś może dać mi redukcję FPT, która rzeczywiście działa wykładniczo w parametrze . Dzięki.$k$

Wczesnym przykładem jest dowód twardości W [2] dla Dominującego Zestawu Turniejowego (Twierdzenie 4.1 w [1]). Redukcja pochodzi z zestawu dominującego i konstruuje turniej z wierzchołkami , gdzie n jest liczbą wierzchołków dominującego zbioru, a k jest parametrem.$O(2^k n)$$n$$k$

[1]: Rodney G. Downey i Michael R. Fellows. Sparametryzowana wykonalność obliczeniowa. W P. Clote i JB Remmel, redaktorzy, Proceedings of Feasible Mathematics II, strony 219–244. Birkhauser, 1995.

Poniższy artykuł zawiera redukcje dla różnych parametryzacji najbliższego podłańcucha, w których czas działania zależy wykładniczo lub podwójnie wykładniczo od parametru (i ta zależność wydaje się nieunikniona).

D. Marks. Najbliższe problemy z podciągiem przy małych odległościach . SIAM Journal on Computing, 38 (4): 1382-1410, 2008.

Jako uzupełnienie innych odpowiedzi poniższa propozycja pokazuje, że odpowiadające sobie pojęcia redukowalności są nieporównywalne:

$(Q,k)$$(Q',k')$$(Q,k) <^{\mathrm{fpt}} (Q',k')$$Q' <^{\mathrm{ptime}}\ Q$

$<^{\mathrm{fpt}}$$<^{\mathrm{ptime}}$

[2]: J. Flum, M. Grohe. Sparametryzowana teoria złożoności. Springer (2006)

Prawdopodobnie nie jest to zamierzona odpowiedź, ale co powiesz na (odmienny wariant) kodowania kolorów dla problemu ścieżki k? http://en.wikipedia.org/wiki/Color-coding

Tam transformuje się instancję problemu ścieżki k na instancje problemu kolorowej ścieżki k poprzez redukcję fpt z zależnością super wielomianową od k. (Jeden tworzy wiele instancji, ale można je postrzegać jako jedną dużą instancję.) Ponieważ kolorowy problem ścieżki k można rozwiązać w czasie fpt za pomocą programowania dynamicznego, możemy stwierdzić, że problem ścieżki k należy do FPT.

Innym przykładem takiej redukcji jest dowód twardości dla wymiaru VC. Zobacz „Sparametryzowana złożoność uczenia się” autorstwa Downey, Evans i Fellows.