2
$\begingroup$

I am not sure if this is a cheap query. However I am unable to find this myself. So I am posting here. The standard complexity class is built with $NP$ and $coNP$ and leads up to $PSPACE$. The reference https://link.springer.com/content/pdf/10.1007%2FBF01184809.pdf gives some classes for which we have oracles with respect to which $UP$ is not low.

  1. Which classes are known to be low with $UP$ oracle ($PSPACE$ is one of them)?

  2. Is there a hierarchy to concoct with $UP$ and $coUP$ analogous to the standard polynomial hierarchy and in particular is there an analog of $PSPACE$?

$\endgroup$
  • 2
    $\begingroup$ I know that if ${\bf UP}$ is low for ${\bf \#P}$ then ${\bf UP} = {\bf CoUP}$. You can read it here = J. KOBLER, U. SCHONING, AND J. TORAN, On counting and approximation, Acta Inform. 26 (1989), 363-379. $\endgroup$ – Tayfun Pay Jul 8 at 2:47
  • 1
    $\begingroup$ @TayfunPay Very interesting. Then likely that there is an unambiguous version of things and a fewbiguous version of things. $\endgroup$ – T.... Jul 8 at 9:44
2
$\begingroup$

Problem 2. answered in references

a. https://arxiv.org/pdf/cs/9907033.pdf

b. http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=19DD617ABDB31709CA0BEF797C283867?doi=10.1.1.60.9357&rep=rep1&type=pdf.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.