Vermutung: Alle FPT NP-vollständigen Sprachen sind isomorph mit festen Parametern

Berman-Hartmanis-Vermutung: Alle NP-vollständigen Sprachen sehen gleich aus, in dem Sinne, dass sie durch polynomielle Zeitisomorphismen miteinander in Beziehung gesetzt werden können [1].

Ich interessiere mich für eine feinkörnigere Version der "Polynomzeit", wenn wir parametrisierte Reduktionen verwenden.

Ein parametrierte Problem ist eine Teilmenge von , wobei Σ eine endliche Alphabet und Z ≥ 0 ist der Satz von nicht - negativen Zahlen. Eine Instanz eines parametrisierten Problems ist daher ein Paar ( I , k ) , wobei k der Parameter ist.$Σ^∗ × Z \geq 0$$Σ$$Z\geq 0$$(I, k)$$k$

Ein parametrisierter Problem wird fester Parameter reduzierbar auf ein parametrisierte Problem π 2 , wenn es vorhanden Funktionen f , g : Z ≥ 0 → Z ≥ 0 , Φ : Σ * × Z ≥ 0 → Σ * und ein Polynom p ( · ) so dass für jeden Fall ( I , k ) von π 1 , ( Φ ( I $π_1$$π_2$$f$$g$$Z≥0 → Z≥0$$Φ : Σ∗ × Z≥0 → Σ^∗$$p(·)$$(I, k)$$π_1$ ist eine Instanz von π 2, die in der Zeit f ( k ) · p ( | I | ) und ( I , k ) ∈ π 1 genau dannberechenbar ist,wenn ( Φ ( I , k ) , g ( k ) ) ∈ π$(Φ(I, k), g(k))$$π_2$$f(k) · p(|I|)$$(I, k) ∈ π_1$$(Φ(I, k), g(k)) ∈ π_2$. Zwei parametrisierte Probleme sind mit festen Parametern äquivalent, wenn sie mit festen Parametern auf einander reduzierbar sind.

Einige NP-vollständige Probleme sind FPT, zum Beispiel ist die Entscheidungsversion des Vertex-Cover-Problems NP-Complete, es hat einen -Algorithmus [2]. Das Finden besserer Reduzierungen fester Parameter eines FPT-Problems, das NP-vollständig ist, kann zu einem besseren Algorithmus führen, beispielsweise durch Aufrufen einer Reduktion auf eine "obige Garantieversion" des Multiway Cut-Problems kann zu einem Algorithmus in der Zeit O ∗ führen ( 4 k ) für das AGVC-Problem (Above Guarantee Vertex Cover) [3], das besser ist als der ursprüngliche O ∗ ( 15 k ) -Algorithmus [4].$O(1.2738^k + kn)$$O^*(4^k)$$O^*(15^k)$

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

Ist diese Vermutung wahr?

[1] Berman, L.; Hartmanis, J. (1977), "Über Isomorphismen und Dichte von NP und anderen vollständigen Mengen", SIAM Journal on Computing 6 (2): 305–322.

[2] J. Chen, IA Kanj und G. Xia, Verbesserte Obergrenzen für die Scheitelpunktabdeckung, Theor.Comput. Sci., 411 (2010), S. 3736–3756.

[3] M. Cygan, M. Pilipczuk, M. Pilipczuk und JO Wojtaszczyk, On Multiway Cut, parametrisiert über den unteren Grenzen, in IPEC, 2011.

[4] M. Mahajan und V. Raman, Parametrisierung über garantierten Werten: Maxsat und Maxcut, J. Algorithms, 31 (1999), S. 335-354.

Serge Gaspers hat bereits erwähnt, warum Ihre Vermutung trivial wahr ist.
Tatsächlich kann man jedoch Isomorphismen mit festen Parametern für die Polynomzeit erhalten , von
denen ich jetzt weiß, dass sie nicht viel weniger trivial sind, da sie für jedes
geordnete Paar nicht trivialer FPT-Probleme mit einer Reduktion im gewöhnlichen Sinne gelten.

$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$$\:$ Daher erfüllt es Ihre Festparameterbedingung.