DAA - Cooks Theorem
Stephen Cook stellte in seiner Arbeit „The Complexity of Theorem Proving Procedures“ vier Theoreme vor. Diese Sätze sind unten angegeben. Wir verstehen, dass in diesem Kapitel viele unbekannte Begriffe verwendet werden, aber wir haben keinen Spielraum, um alles im Detail zu diskutieren.
Es folgen die vier Sätze von Stephen Cook -
Satz-1
Wenn ein Satz S von Strings wird dann von einer nicht deterministischen Turing-Maschine innerhalb der Polynomzeit akzeptiert S ist P-reduzierbar auf {DNF-Tautologien}.
Satz-2
Die folgenden Mengen sind paarweise P-reduzierbar (und haben daher jeweils den gleichen polynomiellen Schwierigkeitsgrad): {Tautologien}, {DNF-Tautologien}, D3, {Subgraphenpaare}.
Satz 3
Für jeden TQ(k) vom Typ Q, $ \ mathbf {\ frac {T_ {Q} (k)} {\ frac {\ sqrt {k}} {(log \: k) ^ 2}}} $ ist unbegrenzt
Da ist ein TQ(k) vom Typ Q so dass $ T_ {Q} (k) \ leqslant 2 ^ {k (log \: k) ^ 2} $
Satz-4
Wenn die Menge S von Strings von einer nicht deterministischen Maschine innerhalb der Zeit akzeptiert wird T(n) = 2n, und wenn TQ(k) ist eine ehrliche (dh in Echtzeit abzählbare) Funktion des Typs Qdann gibt es eine Konstante K, damit S kann von einer deterministischen Maschine innerhalb der Zeit erkannt werden TQ(K8n).
Zunächst betonte er die Bedeutung der Reduzierbarkeit der Polynomzeit. Dies bedeutet, dass bei einer Polynomzeitverkürzung von einem Problem zum anderen sichergestellt wird, dass jeder Polynomzeitalgorithmus aus dem zweiten Problem in einen entsprechenden Polynomzeitalgorithmus für das erste Problem konvertiert werden kann.
Zweitens konzentrierte er sich auf die Klasse NP von Entscheidungsproblemen, die in polynomieller Zeit von einem nicht deterministischen Computer gelöst werden können. Die meisten unlösbaren Probleme gehören zu dieser Klasse, NP.
Drittens hat er bewiesen, dass ein bestimmtes Problem in NP die Eigenschaft hat, dass jedes andere Problem in NP polynomiell darauf reduziert werden kann. Wenn das Erfüllbarkeitsproblem mit einem Polynomzeitalgorithmus gelöst werden kann, kann jedes Problem in NP auch in Polynomzeit gelöst werden. Wenn ein Problem in NP unlösbar ist, muss das Erfüllbarkeitsproblem unlösbar sein. Somit ist das Erfüllbarkeitsproblem das schwierigste Problem bei NP.
Viertens schlug Cook vor, dass andere Probleme in NP mit dem Erfüllbarkeitsproblem dieser Eigenschaft, das härteste Mitglied von NP zu sein, teilen könnten.