How to proof UNIQUE-SAT is in $\Delta^p_2$ or in $P^{sat}$
1) when given a bool formula can I ask oracle whether the given formula has at least one satisfying truth assignment and whether it has at least two?
2) Is UNIQUE-SAT in NP?
$\begingroup$
$\endgroup$
0
Add a comment
|
$\begingroup$
$\endgroup$
UNIQUE-SAT is complete for the complexity class US. It is not hard to reduce coSAT to UNIQUE-SAT (by adding a trivial satisfying assignment), and so if UNIQUE-SAT is in NP, it would imply that NP=coNP, which is considered unlikely. There is a randomized reduction from SAT to UNIQUE-SAT, which implies that UNIQUE-SAT∉P unless NP=RP.
A SAT oracle can only answer one type of question: is the given formula satisfiable or not. However, you can use it to answer other questions. For example, in order to determine whether there are at least two satisfying assignments for some formula $\varphi$, you can ask whether the following formula is satisfiable: $\varphi(x) \land \varphi(y) \land x \neq y$ (you can convert this into CNF).
answered Dec 28 '17 at 17:00
