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.

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$$\:$