Sign up ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

${\sf UP}$ is defined in terms of unambiguous-SAT which asks if there exits at most one solution or no solution. On the other hand, ${\sf US}$ is defined in terms of unique-SAT which asks if there exists exactly one solution. I would like to know whether it is known that they are Turing equivalent, ${\sf P^{UP}}={\sf P^{US}}$. Any references would be appreciated.

share|cite|improve this question
$US$ contains $coNP$, so $P^{US}$ is at least as powerful as $P^{coNP}=P^{NP}$. The (mostly) common wisdom suggests that $P^{UP}$ is strictly contained in $P^{NP} \subseteq P^{US}$. – Joshua Grochow Nov 17 '12 at 2:57

1 Answer 1

up vote 10 down vote accepted

[Since it's been a while and no one has added any further answers, I'm reposting my comment as an answer.]

${\sf US}$ contains ${\sf coNP}$, so ${\sf P^{US}}$ is at least as powerful as ${\sf P^{coNP}} = {\sf P^{NP}}$. The (mostly) common wisdom suggests that ${\sf P^{UP}}$ is strictly contained in ${\sf P^{NP}} \subseteq {\sf P^{US}}$.

share|cite|improve this answer
Under the assumption that ${\bf P} = {\bf NP}$, is it true that there exits a deterministic polynomial time algorithm such that given a SAT formula with x satisfying truth assignments we can get a formula with a unique satisfying truth assignment? That is does Valiant Vazirani reduction turn into a deterministic polynomial time reduction when ${\bf P} = {\bf NP}$? Also, isn't ${\bf UP}$ and ${Promise \bf UP}$ are interchangeable as oracles the same way ${\bf NP}$ and ${SAT}$ are interchangeable as oracles. – Tayfun Pay Jun 17 '13 at 0:07
@TayfunPay: If P=NP, then you can just check if $\varphi$ is satisfiable, and if so output the formula $x_1 \wedge \dotsb \wedge x_n$ which clearly has a unique satisfying assignment, and otherwise output $x_1 \wedge \neg x_1$. In regards to your other questions, no, UP and PromiseUP are not interchangeable as oracles (, To see why not, think about what UP language you would use as an oracle for Valiant-Vazirani. – Joshua Grochow Jun 21 '13 at 3:00
Okay. Thank You for your reply. Little more. If ${\bf P} = {\bf NP}$ then ${\bf UP}$ would be in ${\bf P}$ so we could solve promise_UP in polynomial time since promise_UP is the class of promise problems solvable by an UP machine... Also if ${\bf P} = {\bf NP}$ then ${\bf RP}$ would be in ${\bf P}$ as well then this implies that Valiant Vazirani could be done in "deterministic" polynomial time? That is what I was getting at. Thank you – Tayfun Pay Jun 21 '13 at 18:12
@TayfunPay: Yes, if P=NP then VV can be done completely deterministically. My first point was just that if P=NP, then one can get the same effect as VV (isolating a witness) much easier than in VV itself. – Joshua Grochow Jun 25 '13 at 21:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.