5
$\begingroup$

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)

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ Anything complete a little ways up the polynomial hierarchy works. You may need to add more constraints to get an interesting answer. $\endgroup$
    – Geoffrey Irving
    Jul 11, 2014 at 17:42
  • 4
    $\begingroup$ That's quite a list of constraints. What motivates that choice? $\endgroup$
    – Niel de Beaudrap
    Jul 11, 2014 at 17:50
  • $\begingroup$ Oops, my comment is wrong: I didn't notice that NP-hard was disallowed. $\endgroup$
    – Geoffrey Irving
    Jul 11, 2014 at 18:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – Robin Kothari
    Jul 11, 2014 at 18:02
  • $\begingroup$ Hi, thanks for reply. Yes, NP-hard is disallowed. $\endgroup$
    – XORwell
    Jul 11, 2014 at 18:30

3 Answers 3

Reset to default
14
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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