Gibt es ein NP-Hard-Problem, für den kein fester Parameter-traktiver Algorithmus vorhanden ist?

Question

Frage

gibt es ein NP-Hard-Problem, für den wir einen Parameter ^{1 hinzufügen können, um ein "natürliches" -Sup-Problem zu erstellen, für den kein FPT-Algorithmus vorhanden ist?}

.
1. das Hinzufügen eines Parameters ist erforderlich, da ein NP-Hard-Problem normalerweise nur eine Frage mit einer Ja- oder Nein-Antwort ist, wenn Sie einen Parameter einschränken möchten, den Sie angeben müssen, welche Sie angeben müssen, welche ein (obwohl so etwas wie $ K $ -Coloring könnte bereits einen offensichtlichen Bereich haben), so dass mit" Angeben dessen Parameter "eine einschränkend ist, ein" Hinzufügen eines Parameters "auf das Problem. Eine detailliertere Beschreibung ist in der Antwort von der diskreten Eidechse enthalten.
2. Ich denke, dass Natürliche versucht, "triviale" Parametrierungen auszuschließen, während ich meinen ersten Zweifeln in dieser Frage diskutiere. Eine detailliertere Beschreibung ist wiederum in der Antwort von diskreten Eidechse enthalten.

Zweifel

0. Es könnte eine triviale Frage sein, da es vielleicht möglich ist, das gesamte Problem in der $ F (k_1, k_2, .., k_m) $ Teil der $ F (K_1, K_2, .., K_M) N ^ C $ Algorithmus während der Einstellung $ n= c '$ Wobei $ C' $ eine beliebige Konstante ist. Vielleicht verhindert die genaue Definition von FPT eine solche (AB) Verwendung des Konzepts von FPT.

Auf der Grundlage des Kommentars von PLOP gibt es in der Tat eine triviale Methode, um "beliebig" parametrieren "(ich übernehme jedes ordnungsgemäß gut gestellte Problem) Problem, so dass seine Parametrierung FPT ist. Diese Parametrierungen verwenden Sprachen, die ich davon ausgreife, was beschrieben wird, was beschrieben wird hier . Eine solche "Trivial" (angesichts der Frage, nicht angesichts der Schwierigkeit) soll die Parametrierung ignoriert werden. So in den "Worten" der diskreten Eidechse: Nicht triviale Parameterbereiche (s) ist (sind) beabsichtigt.

Answer 1

Sie müssen hier ein bisschen vorsichtig sein. Beachten Sie, dass ein NP-Hard-Problem ein Entscheidungsproblem ist, während FPT-Algorithmen parametrisierte -E-Entscheidung oder Suchprobleme löst. Die Frage ist also etwas schlecht geformt. Ich denke jedoch, die Frage, die Sie wahrscheinlich fragen wollten, ist:

gibt es ein NP-Hard-Problem, für den wir einen Parameter ^{1 hinzufügen können, um ein "natürliches" -Sup-Problem zu erstellen, für den kein FPT-Algorithmus vorhanden ist?}

an welchen Antwort ist (bedingungslos!) Ja .

Beachten Sie zunächst, dass FPT, die Klasse von Problemen, die über einen fixierbaren, fixierbaren Algorithmus lösbar sind, eine ordnungsgemäße Teilmenge von XP, die Klasse von "Slice-Wise-polynomen" parametrierten Problemen ist, die von einem Polynom gelöst werden können -Time-Algorithmus, wenn der Parameter behoben ist. Mit anderen Worten: $ \ mathrm {ftt} \ subsetneq \ mathrm {xp} $ . (Ich muss gestehen, dass ich den Beweis nicht von "Standarddiagonalisierung" anbieten kann, die meine Quelle als einzige Rechtfertigung anbietet. Vielleicht kann mir ein Komplexitätstheoretiker helfen)

Nächstes Beachten Sie, dass, da mindestens ein Problem in XP nicht von einem FTPT-Algorithmus gelöst werden kann, jeder XP-Hard (im Sinne von FPT-Reduktionen) nicht von einem FTPT-Algorithmus gelöst werden kann.

im Kapitel "Nachweisbarer Intractability: die Klasse XP" in Downey und Fellows ' Grundlagen der parametrisierten Komplexität vervollständigen sie das Argument, indem sie zeigen, dass das, was sie das Pebble-Spielproblem nennen ist XP-Hard durch "Neuinterpretieren" ein Problem, das bekannt ist, dass er zumindest pspace-hard ist (nach dem Entfernen des Parameters "), so sicherlich np-hart. Weitere Informationen finden Sie dort ein Buchkapitel.

---

Lassen Sie mich hinzufügen, dass dieses Ergebnis auch sehr überraschend war, denn für die meisten praktischen -Probleme benötigen wir Al-Arten von Vermutungen ( $ P \ NEQ NP $ , ETH, Seth, 3-Summe usw.), aber dieses Ergebnis ist eine eigentliche Tatsache, die unabhängig von jeder Vermutung ist.

---

_{1: Um zu klären, durch "Hinzufügen eines Parameters", meine ich mit einem NP-Hard-Problem $ l \ Subseteq \ Sigma ^ * $ , Definieren Sie ein parametrisiertes Problem $ l '\ Subseteq \ Sigma ^ * \ times \ mathbb {n} $ als $ l':={\ langle x, k \ rangle \ mid f (x)= k \} $ für einige function $ F: \ sigma ^ * \ rightarrow \ mathbb { N} $ . Dies erfasst die intuitive Idee, dass der zusätzliche Parameter eine Eigenschaft der Eingabe misst.
2: Die Definition in 1 ermöglicht immer noch alle möglichen seltsamen Parametrierungen mit Funktionen wie $ F (x) \ Equiv 1 $ . Idealerweise benötigen wir $ F $ , um etwas Sinnvolles über die Instanz zu messen, aber das scheint schwer zu formalisieren. Ich konnte mir keine andere Formalisierung vorstellen, die alle "unnatürliche" Parametrierungen entfernen. Also werde ich den informellen Vorstellung von "natürlichen parametrierten Problemen" von Downey- und Fellows-Buch kopieren.}

Answer 2

Ich würde ja sagen, aber Sie müssen die Bedingung annehmen, dass P $ \ neq $ np. Nehmen Sie $ K $ -Coloring, wo wir feststellen möchten, ob ein Diagramm mit $ K $ gefärbt werden kann Farben so, dass zwei verbundene Scheitelpunkte nicht die gleiche Farbe haben. Wir können eindeutig 3-Färbung auf $ K $ -Coloring reduzieren.

Angenommen, $ K $ -Coloring ist in FPT, dann gibt es einen Algorithmus, der dieses Problem in $ f löst ( k) \ cdot n ^ {o (1)} $ . Wenn wir $ k= 3 $ einstellen, erhalten wir einen Polynom-Zeit-Algorithmus, und somit kann ein 3-Färbing in Polynom-Zeit gelöst werden, es sei denn, P $ \ neq $ np. Offensichtlich, wenn P $ \ neq $ np, dann gibt es keinen FPT-Algorithmus für $ K $ -Coloring .

Wenn Sie nach etwas strengerem in dem Sinne suchen, dass es absolut nicht existieren kann, dann bin ich nicht sicher, ob ein solches Problem gefunden wurde.

Answer 3

Vielleicht eine andere Option, die deutlich schwächer als die Lösung von Stanja und diskreten Lizards-Lösung, unternimmt die exponentielle Zeithypothese (ETH). ETH übernimmt $ ft \ neq w [1] $ (oder nehmen Sie einfach nur FTPT $ \ neq $ w [1] direkt).

also mit ft $ \ neq $ w [1] man übernimmt keine (nicht triviale) Parametrierung $ kd $ eines W [1] -Hard-Problems ist FPT. Ein Beispiel für AW [1] Hartproblem, das NP-Hard * ist, ist $ k-clique $ , so dass es AW [1] -Hard-Problem gibt, das ein NP ist -hard-Problem. Seit (nicht trivialer) Parametrierung $ kd $ w [1] -hard-Probleme sind nicht (in) FPT mit Annahme FPT $ \ neq $ w [1], das bedeutet, eine beliebige (nicht triviale) Parametrierung $ kd $ von NP-Hard-Problem $ k-clique $ ist nicht ft. Das heißt, wenn FPT $ \ neq $ w [1], gibt es ein NP-Hard-Problem, das nicht ft ist.

.
• das Entscheidungsproblem ( $ K $ ) - Clique ist NP-Complete , daher ist es auch np-fleißig, da das Bild unten zeigt:

Haftungsausschluss

Ich kam mit diesem Argument nicht auf, es ist im Grunde der Kommentar der diskreten Eidechse, und es ist fast so, als würde man die Frage beantworten: "Gibt es $ A $ existieren ? " mit: "Ich gehe davon aus, dass $ B $ existiert, oh, da ist ein $ A $ das in Set ist $ B $ , und da ich angenommen habe, dass $ B $ existiert, muss auch eine $ A $ , also ja gibt es einen $ a $ . (Wie wird auch von der diskreten Eidechse in den Kommentaren erläutert)