Unterscheidet sich das Problem der Bestimmung, ob ein gegebener Boolescher Ausdruck rechnerisch erfüllt werden kann oder nicht, davon, tatsächlich eine Lösung für den Ausdruck zu finden?
Mit anderen Worten, gibt es eine andere Möglichkeit festzustellen, dass ein bestimmter Ausdruck erfüllt werden kann, ohne explizit die 'richtigen Einstellungen' für die Booleschen Variablen zu bestimmen? Oder reduzieren sich alle möglichen Beweise in der Polynomzeit auf die 'richtigen Einstellungen'?
Vergib mir meine Unwissenheit, ich bin nur ein Ingenieurstudent. Wikipedia scheint zu implizieren , dass der Akt des nur Befund SAT oder UNSAT ist NP-vollständig.
Antworten:
Wie in einem Kommentar erwähnt, kann jedes Verfahren zum Bestimmen der Erfüllbarkeit einer Booleschen Formel leicht in ein Verfahren zum Finden der zufriedenstellenden Variablenzuweisung umgewandelt werden. Dies liegt daran, dass alle NP-vollständigen Probleme nach unten selbstreduzierbar sind.
Aus Wikipedia :
Selbstreduzierbarkeit
Das SAT-Problem ist selbstreduzierbar, dh jeder Algorithmus, der korrekt antwortet, wenn eine Instanz von SAT lösbar ist, kann verwendet werden, um eine zufriedenstellende Zuordnung zu finden. Zunächst wird die Frage nach der angegebenen Formel . Wenn die Antwort "Nein" lautet, ist die Formel nicht zufriedenstellend. Andernfalls wird die Frage nach der teilweise instanziierten Formel , dh wobei die erste Variable durch und entsprechend vereinfacht wird. Wenn die Antwort "Ja" lautet, ist , andernfalls ist . Werte anderer Variablen können anschließend auf die gleiche Weise ermittelt werden. Insgesamt sind Läufe des Algorithmus erforderlich, wobeiΦ { x 1 = T R U E } Φ x 1 T R U E x 1 = T R U E x 1 = F A L S E n + 1 n ΦΦ Φ {x1=TRUE} Φ x1 TRUE x1=TRUE x1=FALSE n+1 n ist die Anzahl der verschiedenen Variablen in .Φ
quelle
Die richtige Antwort ist, dass die Bestimmung, ob eine Lösung existiert, und die Bestimmung einer Lösung rechnerisch unterschiedlich sind. Nicht alle Methoden zur Bestimmung, ob eine Lösung vorhanden ist, können eine Lösung ergeben. Es gibt eine Lösung für das Hamilton-Pfad-Problem, die bestimmen kann, ob ein Pfad vorhanden ist, aber keinen solchen Pfad erzeugen kann. Die Frage wird jedoch von arxiv.org/abs/cs/0205064 zur Diskussion gestellt.
quelle