Ist "Erreichbares Objekt" wirklich ein NP-vollständiges Problem?

Ich habe dieses Papier gelesen , in dem die Autoren Satz 1 erklären, in dem es heißt, dass "erreichbares Objekt" (wie im Papier definiert) NP-vollständig ist. Sie beweisen jedoch die Reduktion nur in eine Richtung, dh von 2P1N SAT zu erreichbarem Objekt. Dies beweist nur, dass das Problem NP-schwer ist; Müssen wir nicht die umgekehrte Richtung (2P1N zum erreichbaren Objekt) beweisen, um die NP-Vollständigkeit zu beweisen?

complexity-theory np-complete np-hard satisfiability Unendlichkeit
quelle

Die Autoren haben nicht bewiesen, dass das Problem in NP liegt, sie haben nur behauptet, dass dies der Fall ist (und dass es leicht ist, dies zu beweisen). Sie haben NP-Härte bewiesen.

Diskrete Eidechse

Ich möchte nur, dass Sie wissen, dass das Symbol \innicht ist \epsilon.

Alice Ryhl

Antworten:

Ein Problem $P$ ist NP-vollständig, wenn:

$P$ ist NP-hart und
$P \in \textbf{NP}$ .

Die Autoren geben einen Beweis für Artikel Nummer 1. Artikel Nummer 2 ist wahrscheinlich offensichtlich (und sollte dem Publikum der Zeitung klar sein). Für den Nachweis von Artikel Nr. 1 benötigen Sie nur eine (Viel-Eins-) Reduzierung von einem NP-vollständigen Problem (z. B. SAT) auf $P$ ; Es besteht keine Notwendigkeit, eine Reduktion in die entgegengesetzte Richtung zu konstruieren.

dkaeae
quelle

Falls jemand immer noch verwirrt ist, ist 2 trivial, da in NP zu sein bedeutet, dass Sie schnell (Polynomzeit) eine Lösung für das Problem überprüfen können. Hier kann eine Lösung überprüft werden, indem einfach die in der Lösung angegebenen Swaps durchgeführt und überprüft werden, ob Sie das gewünschte Objekt erreichen.

Steven Waterman

@StevenLowes Das einzige, was Sie noch überprüfen müssten, ist, dass die Anzahl der erforderlichen Swaps polynomisch ist. Auch das ist nicht so schwer zu sehen, wie ich in meiner Antwort erkläre.

Diskrete Eidechse

Ich hatte das Papier falsch gelesen und angenommen, dass es für eine Sequenz nicht möglich war, mehr als N Swaps zu erfordern - Sie haben Recht :)

Steven Waterman

@StevenLowes: Nun, es sollte auch besser ein Entscheidungsproblem sein (ausgedrückt als). Es gibt NP-harte Probleme, die überhaupt keine Entscheidungsprobleme sind, die offensichtlich nicht in NP auftreten werden, egal wie einfach sie zu "verifizieren" sind.

Kevin

Die Autoren behaupten, dass es leicht zu zeigen ist, dass das Problem in NP liegt. Um diese Behauptung zu beweisen, nehmen Sie eine Folge von Swaps, die zu einem Staat als Zeugen dafür führen, dass der Staat erreichbar ist. Bei einer solchen Folge von Polynomgrößen können wir in Polynomzeit überprüfen, ob der Zustand tatsächlich durch Ausführen der Swaps erreichbar ist.

$n$ $n$ $n^2$

Ich denke, wenn es nicht strenge Präferenzen gäbe, könnte es möglich sein, dass sich einige Elemente über lange Zyklen bewegen müssen, um bestimmte Zustände zu erreichen, und dass es insbesondere Zustände gibt, in denen alle Sequenzen von Swaps eine exponentielle Größe haben. Ich kann mir jedoch kein unmittelbares Beispiel für ein solches Problem vorstellen. Zumindest ist es nicht mehr einfach, das Problem mit nicht strengen Präferenzen in NP zu zeigen.

Diskrete Eidechse
quelle