Wie wurde gezeigt, dass die ersten NP-vollständigen Probleme NP-vollständig waren?

Question

Aus dem Eintrag wikipedia 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 zu reduzieren, „es

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 das Problem kann in Polynomzeit auf einem nicht verifiziert werden -deterministic Turing-Maschine)

2. zeigen, dass ein Problem NP-vollständig ist bereits bekannt sein ‚reduziert‘ auf das neue Problem

Also, meine Frage ist, wie waren die ersten NP- vollständige Probleme "bewiesen", NP-vollständig zu sein? Zu einer Zeit musste die Menge der bekannten NP-vollständigen Probleme Null sein, und dies hätte es unmöglich gemacht, im obigen Prozess auf Schritt 2 zurückzugreifen.

Das lässt mich denken, dass es eine andere Beweismethode gibt, die mir nicht bekannt ist. Entweder das, oder vielleicht wird die gesamte NP-vollständige Eigenschaft wegen des Fehlens einer bekannten polynomialen Zeitlösung für bestimmte Probleme "angenommen". (Eigentlich hätte ich mich nicht wundern, wenn dies der Fall wäre, aber ich hätte gerne eine Art Guru-Feedback).

Answer 1

Cook's Theorem

Die Klasse NP kann als die Klasse von Problemen entscheidbar durch eine nichtdeterministische Turingmaschine in polynomialer Zeit definiert werden. Dieses Theorem zeigt, dass SAT NP-vollständig ist, indem die Operation einer beliebigen nichtdeterministischen Turing-Maschine durch eine boolesche Formel so codiert wird, dass die Maschine genau dann akzeptiert, wenn diese Formel SATisfiable ist.

Historisch gesehen der Begriff der NP-Vollständigkeit zu sprechen, wurde in Richard Karp brech Papier eingeführt (Reducibility Among Combinatorial Problems), wo er NP-Vollständigkeit definiert, verwendet Cooks Satz, und in einem großen Schuss, erwies sich als 21 Probleme NP-vollständig.

Answer 2

Um Ihnen das Wesen des Beweises (die in Garey & Johnsons Computer und Intractibility gehen mehrere Seiten schwer ist):

Jede Rechenproblem als Turingmaschine ausgedrückt werden kann.

Es ist möglich, die Turing-Maschine als ein logisches Problem auszudrücken, das bestimmte Komplexitätsbedingungen erfüllt.

Wenn Sie also das Logikproblem in Polynomialzeit lösen können, können Sie das Turing-Maschinenproblem in polynomieller Zeit lösen.

Dies (zusammen mit einigen anderen Überlegungen) zeigt, dass, wenn Sie das Logikproblem in polynomieller Zeit lösen können, Sie jedes NP-Problem in polynomieller 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.

Das verwendete Logikproblem heißt Satisfiability (oft abgekürzt als SAT). Gegeben eine Reihe von Klauseln der Form (A oder nicht-B oder nicht-C) (Klauseln bestehend aus einer beliebigen Anzahl von Sätzen und Negationen von Sätzen verbunden durch logische oder), gibt es eine Zuordnung von Wahrheitswerten zu den Sätzen, die alle macht die Klauseln wahr?

NP-Vollständigkeit ist eine wohldefinierte Eigenschaft. Der einzige Grund, warum Sie an einem Problem, das NP-vollständig ist, zweifeln, ist, dass Sie dachten, Sie könnten ein anderes NP-vollständiges Problem reduzieren, aber es ist noch nicht gelungen, ein praktisches Problem zu finden oder einen Beweis abzuleiten.

Die Frage ist nicht, ob NP-vollständige Probleme existieren, oder wie ein Problem zu beweisen ist NP-vollständig, aber was das bedeutet. Niemand hat bisher einen polynomiellen Algorithmus zur Lösung eines NP-vollständigen Problems entwickelt, und niemand hat bewiesen, dass ein solcher Algorithmus nicht existieren kann. Ob nun P = NP oder nicht, wir haben sicherlich keine guten Algorithmen, um ein NP-vollständiges Problem zu lösen.

Dies ist eine der Millenium-Probleme der Claypool Foundation. Wenn Sie also einen Beweis vorbringen können, der sich einige sehr helle Leute für einige Jahre entzogen hat, gibt es eine Million Dollar für Sie.