<p>Problem 2. answered in references</p>

<p>a. <a href="https://arxiv.org/pdf/cs/9907033.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/cs/9907033.pdf</a></p>

<p>b. <a href="http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=19DD617ABDB31709CA0BEF797C283867?doi=10.1.1.60.9357&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=19DD617ABDB31709CA0BEF797C283867?doi=10.1.1.60.9357&amp;rep=rep1&amp;type=pdf</a>.</p>

CC BY-SA 4.0
2020-01-09T15:33:04.523Z
Your second reference has a [revision](https://www.sciencedirect.com/science/article/pii/S0304397597000054), which removes an incorrect proof of "Theorem" 5, among other things.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2019-07-09T19:24:48.747Z
2019-07-09T19:24:48.747Z
Turbo
<p>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 <span class="math-container">$NP$</span> and <span class="math-container">$coNP$</span> and leads up to <span class="math-container">$PSPACE$</span>. The reference <a href="https://link.springer.com/content/pdf/10.1007%2FBF01184809.pdf" rel="nofollow noreferrer">https://link.springer.com/content/pdf/10.1007%2FBF01184809.pdf</a> gives some classes for which we have oracles with respect to which <span class="math-container">$UP$</span> is not low.</p>

<ol>
<li><p>Which classes are known to be low with <span class="math-container">$UP$</span> oracle (<span class="math-container">$PSPACE$</span> is one of them)?</p></li>
<li><p>Is there a hierarchy to concoct with <span class="math-container">$UP$</span> and <span class="math-container">$coUP$</span> analogous to the standard polynomial hierarchy and in particular is there an analog of <span class="math-container">$PSPACE$</span>?</p></li>
</ol>

CC BY-SA 4.0
2019-07-08T02:47:55.370Z
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.
Tayfun Pay
CC BY-SA 4.0
2019-07-08T09:44:21.763Z
@TayfunPay Very interesting. Then likely that there is an unambiguous version of things and a fewbiguous version of things.
Turbo
<cc.complexity-theory><reference-request><complexity-classes><oracles><polynomial-hierarchy>
Possibility of hierarchy with $UP$ class?
Turbo
# Possibility of hierarchy with $UP$ class?

(Asked by: username_0 on 2019-07-07)

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

**Tags:** cc.complexity-theory, reference-request, complexity-classes, oracles, polynomial-hierarchy
> **Comments:**
> **username_1**: 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.  
> **username_0**: @TayfunPay Very interesting. Then likely that there is an unambiguous version of things and a fewbiguous version of things.  

---

## 1 answers

### Answer by username_0 on 2019-07-09. Score: 2

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

> **Comments:**
> **username_2**: Your second reference has a [revision](https://www.sciencedirect.com/science/article/pii/S0304397597000054), which removes an incorrect proof of "Theorem" 5, among other things.  

---

