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

11

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

yzll
źródło

Odpowiedzi:

11

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)kn)nk

[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.

Serge Gaspers
źródło
1
(Być może inny) dowód na to samo stwierdzenie można także znaleźć w książce „Parameterized Complexity Theory” J. J. Fluma i M. Grohe, Theorem 7.17.
Mathieu Chapelle,
8

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.

Daniel Marks
źródło
6

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)<fapt(Q,k)Q<ptjammi Q

<fapt<ptjammi

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

Mathieu Chapelle
źródło
5

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.

Yoshio Okamoto
źródło
3

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.

Michael Lampis
źródło