Take the 2-minute tour ×
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|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|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 (cstheory.stackexchange.com/a/17494/129, cstheory.stackexchange.com/a/11171/129). 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.