Is semantic language complexity class UP Turing equivalent to syntactic language complexity class US?

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

• $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

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

• 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