In parametrisierter Komplexität verwenden Menschen die FPT-Reduktion (Fixed-Parameter-Tractable), um die W [t] -Härte zu beweisen. Theoretisch ist eine FPT-Reduktion keine Polynomzeitreduktion, da sie im Parameter k exponentiell ablaufen kann. In der Praxis sind alle FPT-Reduktionen, die ich gesehen habe, p-Zeit-Reduktionen, was bedeutet, dass W [t] -Härtebeweise fast immer NP-Vollständigkeitsnachweise implizieren.
Ich frage mich, ob mir jemand eine FPT-Reduktion geben kann, die tatsächlich exponentiell im Parameter läuft . Vielen Dank.
Das folgende Dokument enthält Reduzierungen für verschiedene Parametrisierungen von Closest Substring, bei denen die Laufzeit exponentiell oder doppelt exponentiell vom Parameter abhängt (und diese Abhängigkeit scheint unvermeidbar zu sein).
D. Marx. Engste Teilstringprobleme bei kleinen Abständen . SIAM Journal on Computing, 38 (4): 1382–1410, 2008.
quelle
Als Ergänzung zu den anderen Antworten zeigt der folgende Satz, dass die entsprechenden Begriffe der Reduzierbarkeit unvergleichlich sind:
[2]: J. Flum, M. Grohe. Parametrisierte Komplexitätstheorie. Springer (2006)
quelle
Wahrscheinlich ist dies keine beabsichtigte Antwort, aber wie wäre es mit einer (derandomisierten Variante der) Farbcodierung für das k-Pfad-Problem? http://en.wikipedia.org/wiki/Color-coding
Dort transformiert man eine Instanz des k-Pfad-Problems durch eine fpt-Reduktion mit superpolynomieller Abhängigkeit von k in Instanzen des bunten k-Pfad-Problems. (Man erstellt mehrere Instanzen, aber sie können als eine große Instanz angesehen werden.) Da das bunte K-Pfad-Problem durch dynamische Programmierung in kurzer Zeit gelöst werden kann, können wir schließen, dass das K-Pfad-Problem zu FPT gehört.
quelle
Ein weiteres Beispiel für eine solche Reduzierung ist der Härtenachweis für die VC-Dimension. Siehe "Parametrisierte Lernkomplexität" von Downey, Evans und Fellows.
quelle