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.
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.
źródło
Jako uzupełnienie innych odpowiedzi poniższa propozycja pokazuje, że odpowiadające sobie pojęcia redukowalności są nieporównywalne:
[2]: J. Flum, M. Grohe. Sparametryzowana teoria złożoności. Springer (2006)
źródło
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.
źródło
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.
źródło