Komplexität der Entscheidung, ob eine Formel genau 1 zufriedenstellende Zuordnung hat

11

Das Entscheidungsproblem

Bei einer Booleschen Formel , tut φ genau eine erfüllende Belegung haben?ϕϕ

kann gesehen werden, in , U P -hard und c o N P -hard zu sein. Ist etwas mehr über seine Komplexität bekannt?Δ2UPcoNP

sdcvvc
quelle

Antworten:

11

Ihr Problem ist bekannt als das Problem , das ist U S -komplette. Das Problem ist in D p aber nicht bekannt seinen D p -hard unter determinis Polynomialzeitreduktion, wo die Klasse D p = { L 1¯ L 2UNIQUE-SATUSDpDp .Dp={L1L2¯L1,L2NP}

Papadimitriou und Yannakis [1] haben gezeigt, dass die Menge der einzigartig erfüllbaren Formeln in . Dies folgt aus der Definition von D p : Sei L 1 SAT und sei L 2 die Menge von Formeln mit 2 oder mehr zufriedenstellenden Zuordnungen. In Bezug auf die D p -Härte von UNIQUE-SAT gaben Blass und Gurevich [2] eine teilweise Antwort. Zum einen zeigten sie, dass eine nicht relativierende Beweismethode erforderlich wäre, um die Frage zu klären. Valiant und Vazirani [3] ergaben jedoch eine randomisierte Polynomzeitverkürzung von SAT, die eine D p -Härte von zeigteDpDpL1L22DpUNIQUE-SATSATDp unter randomisierten Polynomzeitverkürzungen.UNIQUE-SAT

Wenn bekannt ist, dass das Problem höchstens eine Zuordnung oder keine Zuweisungen hat, wird das Versprechen-Problem . Das Valiant-Vazirani Theorem besagt , dass , wenn es ein Polynomialzeitalgorithmus für EINDEUTIGE-SAT , dann N P = R P . Um ihren Satz zu beweisen, zeigten sie, dass das Versprechungsproblem UNAMBIGUOUS-SAT unter randomisierten Polynomzeitverkürzungen N P -hart ist . Eine Folgerung, die sich aus dem Valiant-Vazirani-Theorem ergibt, ist, dass UNIQUE-SAT für D p unter randomisierten Polynomzeitverkürzungen vollständig ist .UNAMBIGUOUS-SATUNAMBIGUOUS-SATNP=RPUNAMBIGUOUS-SATNPUNIQUE-SATDp


[1] Papadimitriou, Christos H. und Mihalis Yannakakis. "Die Komplexität von Facetten (und einige Facetten der Komplexität)." Vorträge des vierzehnten jährlichen ACM-Symposiums zur Theorie des Rechnens. ACM, 1982.

[2] Blass, Andreas und Yuri Gurevich. "Über das einzigartige Problem der Erfüllbarkeit." Information and Control 55.1 (1982): 80 & ndash; 88.

[3] Valiant, Leslie G. und Vijay V. Vazirani. "NP ist so einfach wie das Erkennen einzigartiger Lösungen." Theoretical Computer Science 47 (1986): 85 & ndash; 93.

Juho
quelle
Danke für die Antwort; Ich fand auch ein Kapitel in einem Buch, das besagt, dass die Existenz einer deterministischen Reduktion offen ist.
SDCVVC