Woher wissen wir, dass ein Problem in NP-vollständig ist, wenn wir nicht alle Probleme in NP kennen?

7

Ein Problem ist NP-vollständig, wenn:

  1. Es ist in NP.
  2. Alle Probleme in NP können sich darauf reduzieren.

Es ist Nummer 2, um die es mir hier geht. Ich wäre sehr überrascht, wenn wir jedes Problem in NP kennen würden. Woher wissen wir unter dieser Annahme sicher, dass ein Problem NP-vollständig ist? Woher wissen wir zum Beispiel, dass es kein Problem gibt, von dem wir nicht wissen, dass es sich auf das Problem der booleschen Zufriedenheit reduziert, aber nicht auf das Clique-Problem? Oder wäre ein solches Problem NP-Intermediate und müsste daher P! = NP existieren?

Jason Baker
quelle
3
Haben Sie ein Lehrbuchkapitel über NP-Vollständigkeit gelesen? Das wird deine Frage beantworten. Lesen Sie über den Beweis, dass SAT NP-vollständig ist. Dies wird in Standardquellen ausführlich behandelt. Sie müssen also mehr Nachforschungen anstellen, bevor Sie hier nachfragen (und Sie müssen beschreiben, welche Nachforschungen Sie in der Frage angestellt haben).
DW
Dies wurde in unserer Referenzfrage beantwortet , aber ich denke, diese Frage hat ihren Wert für die spezifische "Anfänger-Verwirrung", die sie anspricht.
Raphael

Antworten:

13

Wir haben einfach alle Probleme in NP. Jedes Problem in NP wird durch eine nicht deterministische Turing-Maschine gegeben, die in Polynomzeit läuft. Steve Cook (und unabhängig davon Leonid Levin) hat bewiesen, dass SAT NP-vollständig ist, indem er die Aussage "Maschine akzeptiert bei nicht deterministischen Entscheidungen " als logische Formel für jede nicht deterministische Turing-Maschine codiert . Für eine Maschine, die in der Zeit und im Raum läuft , hat die Codierung eine Länge von ungefähr . Wenn also eine Polynomzeit ist, hat die Codierung eine Polynomlänge. Die entsprechende SAT-Formel besagt, dass "für einige MaschineM.xyT.S.Ö(T.S.)M.yM.akzeptiert bei nicht deterministischen Entscheidungen ". Diese Formel ist erfüllbar, wenn akzeptiert .xyM.x

Nachdem nachgewiesen wurde, dass ein Problem NP-vollständig ist, muss diese Codierung nicht erneut durchgeführt werden. Um das ein anderes Problem zu beweisenL. ist NP-hart, es reicht aus, um SAT auf zu reduzieren L.. Jedes Problem in NP kann auf SAT und über die Hilfsreduktion auf reduziert werdenL.. Auf diese Weise werden die Ergebnisse der NP-Härte heutzutage bewiesen, indem einige NP-harte Probleme reduziert werden.

Yuval Filmus
quelle