Skip to main content
added 48 characters in body
Source Link
Suresh Venkat
  • 32.2k
  • 4
  • 97
  • 272

[Since it's been a while and no one has added any further answers, I'm reposting my comment as an answer.]

$US$${\sf US}$ contains $coNP$${\sf coNP}$, so $P^{US}$${\sf P^{US}}$ is at least as powerful as $P^{coNP} = P^{NP}$${\sf P^{coNP}} = {\sf P^{NP}}$. The (mostly) common wisdom suggests that $P^{UP}$${\sf P^{UP}}$ is strictly contained in $P^{NP} \subseteq P^{US}$${\sf P^{NP}} \subseteq {\sf P^{US}}$.

[Since it's been a while and no one has added any further answers, I'm reposting my comment as an answer.]

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

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

Source Link
Joshua Grochow
  • 38.5k
  • 4
  • 134
  • 233

[Since it's been a while and no one has added any further answers, I'm reposting my comment as an answer.]

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