# Problems in $\text{PSPACE} \cap \text{Co-NP-Hard}$

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)

• Anything complete a little ways up the polynomial hierarchy works. You may need to add more constraints to get an interesting answer. Jul 11, 2014 at 17:42
• That's quite a list of constraints. What motivates that choice? Jul 11, 2014 at 17:50
• Oops, my comment is wrong: I didn't notice that NP-hard was disallowed. Jul 11, 2014 at 18:00
• 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. Jul 11, 2014 at 18:02
• Hi, thanks for reply. Yes, NP-hard is disallowed. Jul 11, 2014 at 18:30

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.
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 by Gustav Nordh (2004) for more information.