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

Improve this question
$\endgroup$
2
  • 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
    Commented Jul 8, 2019 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$
    – Turbo
    Commented Jul 8, 2019 at 9:44

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Your second reference has a revision, which removes an incorrect proof of "Theorem" 5, among other things. $\endgroup$
    – Lieuwe Vinkhuijzen
    Commented Jan 9, 2020 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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