Wie wurden die ersten NP-vollständige Probleme NP-vollständig gezeigt werden?

Question

Aus dem Wikipedia-Eintrag auf NP-Complete:

„Der einfachste Weg, um zu beweisen, dass einige neue Problem NP-vollständig ist zunächst zu beweisen, dass es in NP ist, und dann einige bekannte NP-vollständiges Problem, um es zu reduzieren“

Ich bin mir ziemlich sicher, dass ich das verstehen: Wenn ich ein Problem habe, kann ich zeigen, dass es NP-vollständig, wenn ich:

1. zeigt, dass es in NP ist (eine Lösung zu kann das Problem in überprüft werden Polynomzeit auf einem nicht-deterministische Turing-Maschine)

2. Zeigen Sie, dass ein Problem schon kann sein NP-Complete bekannt sein 'Reduziert' auf das neue Problem

Also, meine Frage ist, wie waren die ersten NP-vollständigen Probleme bewährten "NP-vollständig zu sein? Zu einer Zeit, die Menge der bekannten NP-vollständiger Probleme muß Null gewesen sein, und dies würde hat es unmöglich 2 in dem obigen Verfahren zu Schritt zu greifen.

Das macht ich denke, dass es eine andere Methode für den Nachweis, die ich nicht bewusst bin. Entweder das, oder vielleicht die ganze NP-vollständig Eigenschaft wird ‚angenommen‘ für bestimmte Probleme wegen des Mangels an einer bekannten Polynomzeit Lösung. (Eigentlich diese geschrieben zu haben, würde ich nicht überrascht, wenn dies der Fall ist, aber ich würde etwas Guru-Feedback oder so mag).

Answer 1

Cook Satz

Die Klasse NP kann als die Klasse von Problemen entscheidbar durch eine nichtdeterministische Turingmaschine in polynomialer Zeit definiert werden. Dieser Satz zeigt, dass SAT NP-vollständig durch Codierung für den Betrieb von nichtdeterministischen Turing Maschine durch eine Boolesche Formel, in der Weise, dass die Maschine übernimmt, wenn und nur wenn diese Formel ist erfüllbar.

Historisch gesehen der Begriff der NP-Vollständigkeit zu sprechen, wurde in Richard Karp brech Papier eingeführt (

Answer 2

Um Ihnen das Wesen des Beweises (die mehrere Seiten hart geht in Garey & Johnson ist Computer und Intractibility ):

Jedes Rechenproblem kann als Turingmaschine ausgedrückt werden.

Es ist möglich, die Turing-Maschine als ein logisches Problem, erfüllen gewisse Komplexität Zwang auszudrücken.

Wenn Sie also die Logik Problem in polynomialer Zeit lösen können, können Sie das Turing-Maschine Problem in polynomialer Zeit lösen.

Diese (zusammen mit einigen anderen Erwägungen) zeigt, dass, wenn Sie die Logik Problem in polynomialer Zeit lösen können, Sie all NP-Problem in polynomialer Zeit lösen können. Dies ist die Definition von NP-vollständig, das logische Problem ist daher, NP-vollständig, und kann als Grundlage für andere Probleme verwendet werden.

Die Logik Problem verwendet wird Satisfiability genannt (oft SAT abgekürzt). Bei einer Reihe von Abschnitten der Form (A oder nicht-B oder nicht-C) (Klauseln, bestehend aus einer beliebigen Anzahl von Sätzen und Negationen von Sätzen verbunden sind durch logische oder), gibt es eine Zuordnung von Wahrheitswerten zu den Sätzen, die alle macht die Klauseln wahr?

NP-Vollständigkeit ist eine gut definierte Eigenschaft. Der einzige Grund, würden Sie im Zweifel sein, über ein Problem zu sein NP-vollständig ist, dass Sie dachten, Sie eine andere NP-vollständiges Problem, um es reduzieren konnte, aber nicht günstig Problem zu finden oder leiten einen Beweis noch verwaltet werden.

Die Frage ist nicht, ob NP-vollständige Probleme existieren, oder wie ein Problem zu beweisen ist NP-vollständig, aber was das bedeutet. Bisher hat noch niemand eine Polynom-Algorithmus erzeugt ein NP-vollständiges Problem zu lösen, und niemand hat bewiesen, dass ein solcher Algorithmus nicht existieren kann. Unabhängig davon, ob P = NP, wir haben sicherlich keine gute Algorithmen jedes NP-vollständiges Problem zu lösen.

Dies ist einer der Millenium-Probleme der Claypool Foundation, also, wenn Sie mit einem Beweis kommen können, die einige sehr helle Menschen für einige Jahre eluding wurde, gibt es eine Million Dollar in es für Sie.

Answer 3

Um Ihnen das Wesen des Beweises (die mehrere Seiten hart geht in Garey & Johnson ist Computer und Intractibility ):

Jedes Rechenproblem kann als Turingmaschine ausgedrückt werden.

Es ist möglich, die Turing-Maschine als ein logisches Problem, erfüllen gewisse Komplexität Zwang auszudrücken.

Wenn Sie also die Logik Problem in polynomialer Zeit lösen können, können Sie das Turing-Maschine Problem in polynomialer Zeit lösen.

Diese (zusammen mit einigen anderen Erwägungen) zeigt, dass, wenn Sie die Logik Problem in polynomialer Zeit lösen können, Sie all NP-Problem in polynomialer Zeit lösen können. Dies ist die Definition von NP-vollständig, das logische Problem ist daher, NP-vollständig, und kann als Grundlage für andere Probleme verwendet werden.

Die Logik Problem verwendet wird Satisfiability genannt (oft SAT abgekürzt). Bei einer Reihe von Abschnitten der Form (A oder nicht-B oder nicht-C) (Klauseln, bestehend aus einer beliebigen Anzahl von Sätzen und Negationen von Sätzen verbunden sind durch logische oder), gibt es eine Zuordnung von Wahrheitswerten zu den Sätzen, die alle macht die Klauseln wahr?

NP-Vollständigkeit ist eine gut definierte Eigenschaft. Der einzige Grund, würden Sie im Zweifel sein, über ein Problem zu sein NP-vollständig ist, dass Sie dachten, Sie eine andere NP-vollständiges Problem, um es reduzieren konnte, aber nicht günstig Problem zu finden oder leiten einen Beweis noch verwaltet werden.

Die Frage ist nicht, ob NP-vollständige Probleme existieren, oder wie ein Problem zu beweisen ist NP-vollständig, aber was das bedeutet. Bisher hat noch niemand eine Polynom-Algorithmus erzeugt ein NP-vollständiges Problem zu lösen, und niemand hat bewiesen, dass ein solcher Algorithmus nicht existieren kann. Unabhängig davon, ob P = NP, wir haben sicherlich keine gute Algorithmen jedes NP-vollständiges Problem zu lösen.

Dies ist einer der Millenium-Probleme der Claypool Foundation, also, wenn Sie mit einem Beweis kommen können, die einige sehr helle Menschen für einige Jahre eluding wurde, gibt es eine Million Dollar in es für Sie.