Wenn ein Problem X (Entscheidungsproblem) als NP-Complete bekannt ist und nachweislich auf das Problem Y reduziert ist, können Sie dann sagen, dass das Problem Y NP-Complete ist?

Question

Wenn ein Problem X (Entscheidungsproblem) als NP-Complete bekannt ist und nachweislich auf das Problem Y in Polynomialzeit reduziert ist, können Sie dann sagen, dass das Problem Y NP-Complete ist?

Mein erster Gedanke war, nein, Problem Y muss gezeigt werden, dass es in NP ist. Aber nach weiterem Nachdenken, wenn X auf Y reduziert wird, wird Y bereits als NP-vollständig betrachtet. Jetzt bin ich nur verwirrt ... jede Hilfe wäre willkommen.

Answer 1

Argumentum pro contrarium:

Wenn X ∈ NP und X ⇔ Y und Y ∉ NP dann X ∉ NP.

Answer 2

Problem X - Ungewiss
Problem Y - In NP

X ist in NP Um zu beweisen, zeigen Sie, dass Sie die Schritte folgen kann jedes Problem in X für ein Problem in Y. zu reduzieren Dann wissen Sie, dass die X-Problem ist mindestens so schwer wie das äquivalente Y-Problem.

Also nein, müssen Sie mit Y beginnen und dann auf X. reduzieren

Answer 3

SAT in einem einzigen Aufruf an alle gelöst werden, aber das bedeutet nicht, dass alle in NP ist.

Answer 4

Ja das ist richtig. Sie können Ihr Problem in polynomieller Zeit auf ein bereits bekanntes NP-vollständiges Problem reduzieren, aber das wird als sehr schwierige Aufgabe angesehen. Stattdessen wählen Sie ein bereits NP-vollständiges Problem und reduzieren es auf Ihr Problem und zeigen auch, dass es in NP ist, dann wird Ihr Problem NP abgeschlossen sein.

Answer 5

Noch nicht, müssen Sie noch ein paar Schritte

Um zu beweisen, dass ein Problem L NP-vollständig ist, müssen wir die folgenden Schritte tun:

1. Beweisen Sie Ihr Problem L gehört NP (dh, dass eine Lösung gegeben Sie es in polynomialer Zeit verifizieren können)
2. Wählen Sie ein bekanntes NP-vollständiges Problem L ‚
3. einen Algorithmus f beschreiben, die L transformiert‘
4. Pro in
L ve, dass Ihr Algorithmus korrekt ist (formal: x ∈ L‘, wenn und nur wenn f (x) ∈ L)
5. dass algo f in Polynomialzeit läuft Beweisen

Bisher haben Sie Schritt 2,3, 4
Sie müssen noch zeigen, dass die Reduktion polynomiell ist (Schritt 5)
Und dass das Problem zu NP gehört (Schritt 1), das heißt eine Lösung kann in polynomieller Zeit verifiziert werden.