Гипотеза: все FPT-NP-полные языки являются фиксированными параметрами-изоморфными

Гипотеза Бермана – Хартманиса: все NP-полные языки выглядят одинаково в том смысле, что они могут быть связаны друг с другом полиномиальными изоморфизмами времени [1].

Меня интересует более мелкозернистая версия «полиномиального времени», то есть, если мы используем параметризованные сокращения.

Параметризованная задача - это подмножество , где Σ - конечный алфавит, а Z ≥ 0 - множество неотрицательных чисел. Таким образом, экземпляром параметризованной задачи является пара ( I , k ) , где k - параметр.$Σ^∗ × Z \geq 0$$Σ$$Z\geq 0$$(I, k)$$k$

Параметризованная задача является приводимым с фиксированными параметрами к параметризованной задаче π 2, если существуют функции f , g : Z ≥ 0 → Z ≥ 0 , Φ : Σ ∗ × Z ≥ 0 → Σ ∗ и полином p ( · ) такие , что для любого экземпляра ( я , K ) из П 1 , ( Ф ( I $π_1$$π_2$$f$$g$$Z≥0 → Z≥0$$Φ : Σ∗ × Z≥0 → Σ^∗$$p(·)$$(I, k)$$π_1$ является экземпляром π 2, вычислимым за время f ( k ) · p ( | I | ) и ( I , k ) ∈ π 1 тогда и только тогда, когда ( Φ ( I , k ) , g ( k ) ) ∈ π$(Φ(I, k), g(k))$$π_2$$f(k) · p(|I|)$$(I, k) ∈ π_1$$(Φ(I, k), g(k)) ∈ π_2$, Две параметризованные задачи эквивалентны с фиксированными параметрами, если они сводимы с фиксированными параметрами друг к другу.

Некоторые NP-полные задачи являются FPT, например, решающая версия задачи покрытия вершин NP-Complete, она имеет алгоритм [2]. Нахождение лучших сокращений с фиксированными параметрами задачи FPT, которая является NP-Complete, может привести к лучшему алгоритму, например, вызывая сокращение к «версии с гарантией выше» задачи Multiway Cut, может привести к алгоритму во времени O ∗ ( 4 k ) для задачи AGVC (покрытие вершины над гарантией) [3], которая лучше, чем исходный алгоритм O ∗ ( 15 k ) [4].$O(1.2738^k + kn)$$O^*(4^k)$$O^*(15^k)$

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

Это предположение верно?

[1] Berman, L .; Хартманис, J. (1977), «Об изоморфизмах и плотности NP и других полных наборов», SIAM Journal of Computing 6 (2): 305–322.

[2] Дж. Чен, И. А. Кандж и Г. Ся, Улучшенные верхние границы для покрытия вершин, Theor.Comput. Sci., 411 (2010), с. 3736-3756.

[3] М. Сиган, М. Пилипчук, М. Пилипчук, Ю. О. Войтащик. О параметрированном многомерном разрезе выше нижних границ, в IPEC, 2011.

[4] М. Махаджан и В. Раман, Параметризация выше гарантированных значений: Maxsat и maxcut, J. Algorithms, 31 (1999), pp. 335-354.

Серж Гасперс уже упоминал, почему ваша гипотеза тривиальна.
Однако на самом деле можно получить изоморфизмы с фиксированным параметром за полиномиальное время ,
которые, как я теперь понимаю, не намного менее тривиальны, поскольку они применимы к каждой
упорядоченной паре нетривиальных задач FPT с сокращением в обычном смысле.

$c$$\pi_1$
$Y$$N$$\pi_2$
$\pi_1$$\pi_2$

$\pi_1$$n^{\hspace{.02 in}c}$
$Y$$N$
$\pi_1$$\pi_2$


$\:$$c$$\pi_1$$k$$n$$n^{\hspace{.02 in}c}$$\:$$k$$\:$ Поэтому он удовлетворяет вашему условию с фиксированными параметрами.