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. – Geoffrey Irving Jul 11 '14 at 17:42
• That's quite a list of constraints. What motivates that choice? – Niel de Beaudrap Jul 11 '14 at 17:50
• Oops, my comment is wrong: I didn't notice that NP-hard was disallowed. – Geoffrey Irving Jul 11 '14 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. – Robin Kothari Jul 11 '14 at 18:02
• Hi, thanks for reply. Yes, NP-hard is disallowed. – XORwell Jul 11 '14 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.

The universal theory of the real field is easily seen to be coNP-hard, and Canny proved it to be in PSPACE, but that’s about all that is known about its relationship to common complexity classes.

• For more on this see its dual NP-hard version en.wikipedia.org/wiki/Existential_theory_of_the_reals – David Eppstein Sep 4 '14 at 16:48
• @DavidEppstein: Great work on that article. I’d give you a barnstar, but the WikiLove thingy seems to be constantly broken. – Emil Jeřábek Sep 5 '14 at 13:01
• 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 Sep 5 '14 at 17:27

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.