Domysł: Wszystkie języki FPT NP-complete mają stały parametr izomorficzny

Hipoteza Bermana – Hartmanisa: wszystkie języki NP-zupełne wyglądają podobnie, w tym sensie, że mogą być ze sobą powiązane przez wielomianowe izomorfizmy czasowe [1].

Interesuje mnie bardziej szczegółowa wersja „czasu wielomianowego”, to znaczy, jeśli zastosujemy sparametryzowane redukcje.

Problem sparametryzowany to podzbiór , gdzie jest skończonym alfabetem, a to zbiór liczb nieujemnych. Przykładem sparametryzowanego problemu jest zatem para , gdzie jest parametrem. $Σ^∗ × Z \geq 0$ $Σ$ $Z\geq 0$ $(I, k)$ $k$

Problem sparametryzowany jest parametrem sprowadzalnym do sparametryzowanego problemu jeśli istnieją funkcje , : , i wielomian taki że w każdym przypadku od , jest przykładem obliczeniowego w czasie i jeśli i tylko jeśli . Dwa problemy ze sparametryzowaniem są równoważne ze stałymi parametrami, jeśli można je ze sobą redukować. $π_1$ $π_2$ $f$ $g$ $Z≥0 → Z≥0$ $Φ : Σ∗ × Z≥0 → Σ^∗$ $p(·)$ $(I, k)$ $π_1$ $(Φ(I, k), g(k))$ $π_2$ $f(k) · p(|I|)$ $(I, k) ∈ π_1$ $(Φ(I, k), g(k)) ∈ π_2$

Niektóre problemy NP-zupełne to FPT, na przykład wersja decyzji problemu pokrycia wierzchołka jest NP-Complete, ma algorytm [2]. Znalezienie lepszych redukcji stałych parametrów FPT, które jest NP-Complete, może prowadzić do lepszego algorytmu, na przykład poprzez odwołanie się do „ponadgwarancyjnej wersji” problemu Multiway Cut może prowadzić do algorytmu w czasie dla problemu AGVC (Above Warranty Vertex Cover) [3], który jest lepszy niż oryginalny algorytm [4]. $O(1.2738^k + kn)$ $O^*(4^k)$ $O^*(15^k)$

$\textbf{My Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic.}$

Czy to przypuszczenie jest prawdziwe?

[1] Berman, L .; Hartmanis, J. (1977), „O izomorfizmach i gęstości NP i innych kompletnych zestawach”, SIAM Journal on Computing 6 (2): 305–322.

[2] J. Chen, IA Kanj i G. Xia, Poprawione górne granice osłony wierzchołków, Theor.Comput. Sci., 411 (2010), s. 3736–3756.

[3] M. Cygan, M. Pilipczuk, M. Pilipczuk i JO Wojtaszczyk, Na szlaku wielodrogowym sparametryzowanym powyżej dolnych granic, w IPEC, 2011.

[4] M. Mahajan i V. Raman, Parametryzacja powyżej wartości gwarantowanych: Maxsat i maxcut, J. Al Algorytmy, 31 (1999), s. 335–354.

complexity-classes np-complete fixed-parameter-tractable

— Rupei Xu
źródło

Nie rozumiem, co rozumiesz przez „język kompletny NP FPT”. Nie ma naturalnego pojęcia, że język sam w sobie jest FPT; pytanie brzmi, czy para język / parametr to FPT.

— Huck Bennett,

Zauważ, że redukcja stałych parametrów może po prostu rozwiązać problem FPT i wygenerować trywialną instancję problemu docelowego Tak / Nie.

— Serge Gaspers

Serge Gaspers wspomniał już, dlaczego twoje przypuszczenie jest banalnie prawdziwe.
Jednak faktycznie można uzyskać izomorfizmy o ustalonych parametrach w czasie wielomianowym ,
co teraz zdaję sobie sprawę, że nie jest to wcale mniej trywialne, ponieważ dotyczy każdej
uporządkowanej pary nietrywialnych problemów FPT ze zmniejszeniem w zwykłym sensie.

Niech będzie liczbą całkowitą, która jest większa niż stopień algorytmu FPT dla , i niech i będą odpowiednio tak i nie wystąpieniem . Poniżej przedstawiono redukcję stałych parametrów w czasie wielomianowym z do : $c$ $\pi_1$
$Y$ $N$ $\pi_2$
$\pi_1$ $\pi_2$

Wypróbuj algorytm FPT na dla maksymalnie kroków. Jeśli to daje odpowiedź, wyślij lub jak wskazano w tej odpowiedzi. W przeciwnym razie wypisz wynik zastosowania zwykłego zmniejszenia czasu wielomianu z do . Poprawność i wielomianowe środowisko uruchomieniowe są oczywiste. Ponieważ jest większy niż stopień algorytmu FPT dla , jest tak, że dla każdego ustalonego istnieje tylko skończenie wiele długości wejściowych dla których maksymalny czas działania algorytmu FPT jest nie mniejszy niż $\pi_1$ $n^{\hspace{.02 in}c}$
$Y$ $N$
$\pi_1$ $\pi_2$

$\:$ $c$ $\pi_1$ $k$ $n$ $n^{\hspace{.02 in}c}$ . Zatem dla każdego ustalonego powyższa redukcja ma tylko skończenie wiele wyników. Dlatego spełnia twój warunek o stałym parametrze. $\:$ $k$ $\:$