${\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.

  • 8
    $\begingroup$ $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}$. $\endgroup$ – Joshua Grochow Nov 17 '12 at 2:57

[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}}$.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Tayfun Pay Jun 17 '13 at 0:07
  • 1
    $\begingroup$ @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. $\endgroup$ – Joshua Grochow Jun 21 '13 at 3:00
  • $\begingroup$ 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 $\endgroup$ – Tayfun Pay Jun 21 '13 at 18:12
  • 1
    $\begingroup$ @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. $\endgroup$ – Joshua Grochow Jun 25 '13 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy