<p>Like the Boolean Formula Isomorphism problem, the Group Equations Isomorphism problem is $\mathsf{coNP}$-hard and in $\mathsf{\Sigma_2P}$, for any fixed non-abelian group. See <a href="http://dx.doi.org/10.1007/978-3-540-28629-5_28" rel="nofollow"><em>The Complexity of Equivalence and Isomorphism of Systems of Equations</em></a> by Gustav Nordh (2004) for more information.</p>

CC BY-SA 3.0
2014-09-04T18:04:49.483Z
2014-09-04T18:04:49.483Z
argentpepper
<p>The universal theory of the real field is easily seen to be coNP-hard, and <a href="http://dx.doi.org/10.1145%2F62212.62257" rel="nofollow">Canny</a> proved it to be in PSPACE, but that’s about all that is known about its relationship to common complexity classes.</p>

CC BY-SA 3.0
2014-09-04T16:48:20.460Z
For more on this see its dual NP-hard version https://en.wikipedia.org/wiki/Existential_theory_of_the_reals
David Eppstein
CC BY-SA 3.0
2014-09-05T13:01:43.760Z
@DavidEppstein: Great work on that article. I’d give you a barnstar, but the WikiLove thingy seems to be constantly broken.
Emil Jeřábek
CC BY-SA 3.0
2014-09-05T17:27:37.197Z
Let me mention that while the existential and universal theory of reals are straightforward duals of each other as computational problems, the universal theory is much more natural as a first-order *theory*: depending on the language, it is either the theory of ordered domains or of formally real domains.
Emil Jeřábek
CC BY-SA 3.0
2014-09-04T12:19:43.793Z
2014-09-04T12:19:43.793Z
Emil Jeřábek
<p>Formula Isomorphism is in $\mathsf{\Sigma_2 P} \subseteq \mathsf{PSPACE}$, is easily seen to be $\mathsf{coNP}$-hard, but is not known to be $\mathsf{NP}$-hard. Note that FI is not $\mathsf{\Sigma_2 P}$-complete unless $\mathsf{PH}$ collapses to the third level. All of this can be found in <a href="http://dx.doi.org/10.1137/S0097539798343647">Agrawal &amp; Theirauf</a>. </p>

CC BY-SA 3.0
2014-07-12T02:55:50.827Z
2014-07-12T02:55:50.827Z
Joshua Grochow
<p>I'm in search for examples of decision problems lying in $\text{PSPACE}\cap \text{coNP-hard}$ which are also not (known to be) in $\text{coNP}\cup \text{NP}\cup \text{NP-hard}\cup \text{PSPACE-complete}$.</p>

<p>Is it known any such a problem ? </p>

<p>(It would be very nice to have examples of $\text{PSPACE}\cap\text{coNP-hard}$ combinatorial games with these properties, but any other kind of example would be high appreciated)</p>

CC BY-SA 3.0
2014-07-11T17:42:05.673Z
Anything complete a little ways up the polynomial hierarchy works.  You may need to add more constraints to get an interesting answer.
Geoffrey Irving
CC BY-SA 3.0
2014-07-11T17:50:18.493Z
That's quite a list of constraints. What motivates that choice?
Niel de Beaudrap
CC BY-SA 3.0
2014-07-11T18:00:03.220Z
Oops, my comment is wrong: I didn't notice that NP-hard was disallowed.
Geoffrey Irving
CC BY-SA 3.0
2014-07-11T18:02:20.683Z
Any problem complete for some class that contains co-NP but does not contain NP should work, right? For examples, co-MA, co-AM, co-QMA, co-QCMA, etc.
Robin Kothari
CC BY-SA 3.0
2014-07-11T18:30:51.550Z
Hi, thanks for reply. Yes, NP-hard is disallowed.
XORwell
CC BY-SA 3.0
2014-07-11T22:35:15.053Z
How about ${\bf US}$ or ${\bf C_=P}$?
Tayfun Pay
CC BY-SA 3.0
2014-07-12T02:57:23.567Z
@RobinKothari: Is it an open question (requiring nonrelativizing techniques to resolve) whether the classes you mention have complete problems? I'm pretty sure it is for coMA and coAM, but don't know about the quantum classes (I had the vague impression that the known "complete" problems for the quantum classes were really complete for the promise versions of the classes?).
Joshua Grochow
CC BY-SA 3.0
2014-07-12T13:56:37.587Z
@JoshuaGrochow: Yes, you're right. No complete languages are known for any of the classes I mentioned. I assumed the OP would be fine with promise problems.
Robin Kothari
<cc.complexity-theory><complexity-classes>
Problems in $\text{PSPACE} \cap \text{Co-NP-Hard}$
XORwell
# Problems in $\text{PSPACE} \cap \text{Co-NP-Hard}$

(Asked by: username_0 on 2014-07-11)

I'm in search for examples of decision problems lying in $\text{PSPACE}\cap \text{coNP-hard}$ which are also not (known to be) in $\text{coNP}\cup \text{NP}\cup \text{NP-hard}\cup \text{PSPACE-complete}$.

Is it known any such a problem ?

(It would be very nice to have examples of $\text{PSPACE}\cap\text{coNP-hard}$ combinatorial games with these properties, but any other kind of example would be high appreciated)

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: Anything complete a little ways up the polynomial hierarchy works.  You may need to add more constraints to get an interesting answer.  
> **username_2**: That's quite a list of constraints. What motivates that choice?  
> **username_1**: Oops, my comment is wrong: I didn't notice that NP-hard was disallowed.  
> **username_3**: Any problem complete for some class that contains co-NP but does not contain NP should work, right? For examples, co-MA, co-AM, co-QMA, co-QCMA, etc.  
> **username_0**: Hi, thanks for reply. Yes, NP-hard is disallowed.  
> **username_4**: How about ${\bf US}$ or ${\bf C_=P}$?  
> **username_5**: @RobinKothari: Is it an open question (requiring nonrelativizing techniques to resolve) whether the classes you mention have complete problems? I'm pretty sure it is for coMA and coAM, but don't know about the quantum classes (I had the vague impression that the known "complete" problems for the quantum classes were really complete for the promise versions of the classes?).  
> **username_3**: @JoshuaGrochow: Yes, you're right. No complete languages are known for any of the classes I mentioned. I assumed the OP would be fine with promise problems.  

---

## 3 answers

### Answer by username_5 on 2014-07-12. Score: 14 | Accepted answer

Formula Isomorphism is in $\mathsf{\Sigma\_2 P} \subseteq \mathsf{PSPACE}$, is easily seen to be $\mathsf{coNP}$-hard, but is not known to be $\mathsf{NP}$-hard. Note that FI is not $\mathsf{\Sigma\_2 P}$-complete unless $\mathsf{PH}$ collapses to the third level. All of this can be found in [Agrawal & Theirauf](http://dx.doi.org/10.1137/S0097539798343647).


---

### Answer by username_6 on 2014-09-04. Score: 3

Like the Boolean Formula Isomorphism problem, the Group Equations Isomorphism problem is $\mathsf{coNP}$-hard and in $\mathsf{\Sigma\_2P}$, for any fixed non-abelian group. See [*The Complexity of Equivalence and Isomorphism of Systems of Equations*](http://dx.doi.org/10.1007/978-3-540-28629-5_28) by Gustav Nordh (2004) for more information.


---

### Answer by username_7 on 2014-09-04. Score: 3

The universal theory of the real field is easily seen to be coNP-hard, and [Canny](http://dx.doi.org/10.1145%2F62212.62257) proved it to be in PSPACE, but that’s about all that is known about its relationship to common complexity classes.

> **Comments:**
> **username_8**: For more on this see its dual NP-hard version https://en.wikipedia.org/wiki/Existential_theory_of_the_reals  
> **username_7**: @DavidEppstein: Great work on that article. I’d give you a barnstar, but the WikiLove thingy seems to be constantly broken.  
> **username_7**: Let me mention that while the existential and universal theory of reals are straightforward duals of each other as computational problems, the universal theory is much more natural as a first-order *theory*: depending on the language, it is either the theory of ordered domains or of formally real domains.  

---

