${\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.
Tell me more
×
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.
|
|
|||||
|
|
[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}}$. |
||||
|
|
