${\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.
$\begingroup$
$\endgroup$
1
-
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 GrochowCommented Nov 17, 2012 at 2:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
[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}}$.
answered Dec 16, 2012 at 21:34
-
$\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$ Commented Jun 17, 2013 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$ Commented Jun 21, 2013 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$ Commented Jun 21, 2013 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$ Commented Jun 25, 2013 at 21:26