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)

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

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

$\endgroup$
  • 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 '14 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 '14 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 '14 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.

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