Alle NP-Probleme reduzieren sich auf NP-vollständige Probleme: Wie können NP-Probleme nicht NP-vollständig sein?

10

Mein Buch sagt dies aus

  • Wenn ein Entscheidungsproblem B in P ist und A auf B reduziert wird, dann ist das Entscheidungsproblem A in P.
  • Ein Entscheidungsproblem B ist NP-vollständig, wenn B in NP ist, und für jedes Problem in A in NP reduziert sich A auf B.
  • Ein Entscheidungsproblem C ist NP-vollständig, wenn C in NP ist, und für ein NP-vollständiges Problem B reduziert sich B auf C.

Meine Fragen sind also

  1. Wenn B oder C NP-vollständig ist und alle Probleme in NP unter Verwendung der ersten Regel auf ein NP-vollständiges Problem reduziert werden, wie kann ein NP-Problem nicht NP-vollständig sein?
  2. Wenn A auf B reduziert wird, reduziert sich B auf A?
complexity-theory np-complete decision-problem rubixibuc
quelle
2
Interessante Tatsache in Bezug auf Ihre Nummer 1: Wenn P nicht gleich NP ist, wissen wir, dass es NP-Probleme geben muss, die nicht NP-vollständig sind (dies wird als Ladner-Theorem bezeichnet. Siehe NP-Intermediat ). Das Seltsame ist, dass wir uns nicht sicher sind, welche Rechenprobleme in diese Kategorie passen. Das in Ladners Satz verwendete Problem ist künstlich konstruiert, um den Satz zu beweisen, ist jedoch praktisch unwichtig.
Lucas Cook
4
@Lucas, Factoring und GraphIso sind gemutmaßt NPI zu sein, auch sehen dies .
Kaveh
@Kaveh: Schöne Liste der NPI-Kandidaten, danke! Zur Verdeutlichung habe ich gesagt, dass wir uns eines natürlichen NPI-Problems nicht mit der gleichen Sicherheit wie Ladners Probleme "sicher" sind. Das heißt, wenn , sind die einzigen NPI-Probleme, die mit Sicherheit bekannt sind, künstliche Probleme, die mit der Ladner-Hierarchie zusammenhängen. P.≠N.P.
Lucas Cook

Antworten:

13

Wenn A auf B reduziert wird, reduziert sich B auf A?

Nein. Für ein wirklich erfundenes Beispiel ist jedes mögliche berechenbare Problem A auf das Halteproblem reduzierbar: Übergeben Sie als Eingabe einfach den Algorithmus, der das Problem A löst, aber mit einem while(true)am Ende angehefteten nach dem wahren oder falschen Fall. Wir wissen jedoch, dass das Halting-Problem nicht berechenbar ist und daher nicht auf einen solchen Algorithmus A reduziert werden kann.

Die Grundidee ist, dass man bei einer Reduzierung von A auf B lernen kann, dass B mindestens genauso schwer zu lösen ist wie A und einen Algorithmus benötigt, der mindestens genauso leistungsfähig ist.

Wenn sich also ein Problem A auf ein einfaches Problem B reduziert, können wir ableiten, dass A einfach ist (da die Reduktion uns den effizienten Algorithmus liefert), und wenn ein hartes Problem A auf ein Problem B reduziert wird, können wir schließen, dass B auch schwierig ist ( denn wenn B einfach wäre, müsste A auch einfach sein). Es besteht jedoch immer noch die Möglichkeit, eine dumme Reduktion von einem einfachen Problem zu einem schwierigen Problem vorzunehmen, aber in diesem Fall können wir keine Schlussfolgerungen ziehen.

Hugomg
quelle
8

Wenn B oder C in NP abgeschlossen ist und alle Probleme in NP unter Verwendung der ersten Regel auf ein NP-abgeschlossenes Problem reduziert werden, wie kann ein NP-Problem nicht NP-vollständig sein?

Die erste Regel betrifft Probleme in P. Sie hat nichts mit der Vollständigkeit von NP zu tun. Wenn Problem A NP abgeschlossen ist und Problem B auf A reduziert wird, bedeutet dies nicht , dass B NP abgeschlossen ist.

Wenn A auf B reduziert wird, reduziert sich B auf A?

Nicht generell nein.

sepp2k
quelle
"Nicht allgemein, nein.", Warum? Ein bisschen Erklärung könnte auch für Neulinge nützlich sein. Es sollte auch eine Erklärung für Ihre erste Antwort gegeben werden.
nbro
-1

Ich habe nur die Grundidee bezüglich NPC- und NP-Problemen. Aber alles, was ich kommentieren möchte, ist über "Wenn A auf B reduziert wird, wird B auf A reduziert?"

Betrachten Sie einfach eine Menge A mit {2,3,4,5} Elementen und eine Menge B mit {3,4}. A kann also auf B reduziert werden. B kann jedoch nicht auf A reduziert werden. Stattdessen kann B auf A erweitert werden, wenn B {2,5} Elemente erhält.

Aber wenn A und B dasselbe haben. dann kann A auf B reduziert werden oder B kann auf A reduziert werden.

Naveen CS
quelle
Dies ist überhaupt nicht die richtige Idee der Reduktion. Bei der Reduzierung geht es nicht darum, dass Elemente Elemente gewinnen oder verlieren. Es geht vielmehr darum, eine Instanz eines Problems mithilfe einer Turing-Maschine / eines Turing-Algorithmus in eine andere konvertieren zu können.
Jmite
Okay. Wenn also ein Problem mit einem Algorithmus auf ein anderes reduziert wird, ist es nicht möglich, das Problem aus der reduzierten Ausgabe mit demselben Algorithmus wiederzugewinnen.
Naveen CS
1
Ich bin mir nicht ganz sicher, was du meinst, aber ich denke, es ist nicht möglich. Wenn ich mich nicht irre, können diese Reduzierungen viele zu eins sein. A reduziert sich auf B, wenn eine Polynomanzahl von Aufrufen einer Subroutine, die B löst, ermöglicht, dass A in Polynomzeit gelöst wird. Verschiedene Instanzen von A könnten einen Aufruf derselben Instanz von B
aufrufen
2
Die Frage betrifft Entscheidungsprobleme, nicht Mengen. Wie ist es nützlich, Sets zu betrachten? Die Verwendung des Wortes "reduziert" bedeutet, dass eine Menge eine Obermenge einer anderen ist, ist nicht einmal eine gebräuchliche Terminologie.
Gilles 'SO - hör auf böse zu sein'