4
$\begingroup$

It is known that $\mathsf{NL}=\mathsf{Co{-}NL}$ and unknown if $\mathsf{NP}=\mathsf{Co{-}NP}$. But what about $$\mathsf{NEXP}=\mathsf{Co{-}NEXP}?$$ Is it known whether these two classes are equal?

$\endgroup$

1 Answer 1

8
$\begingroup$

It is known that $\mathsf{NP} = \mathsf{coNP}$ implies $\mathsf{NEXP} = \mathsf{coNEXP}$, using a padding argument. However, both are considered unlikely.

The difference between classes like $\mathsf{NP}$ and $\mathsf{NEXP}$ and the class $\mathsf{NL}$ is that the former are defined by time constraints while the latter is defined by space constraints. The Immerman–Szelepcsényi argument used to prove $\mathsf{NL}=\mathsf{coNL}$ only works for space-constrained classes.

$\endgroup$
5
  • $\begingroup$ That makes perfect sense. Thanks for putting it so clearly! $\endgroup$ May 5, 2016 at 7:49
  • 3
    $\begingroup$ Actually, an Immerman–Szelepcsényi-like argument shows the fun fact $\mathrm{NEXP/poly=coNEXP/poly}$. $\endgroup$ May 5, 2016 at 17:58
  • 1
    $\begingroup$ @EmilJeřábek : ​ ​ ​ In fact, that can easily be strengthened to ​ NE/poly = coNE/poly . ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user12859
    May 5, 2016 at 19:30
  • $\begingroup$ Of course. I stated it for NEXP as that’s what the question is about. $\endgroup$ May 5, 2016 at 20:26
  • $\begingroup$ @RickyDemer Could $\mathsf{NP/poly}=\mathsf{coNP/poly}$ be true? Would this have any implications? $\endgroup$
    – Turbo
    Oct 23, 2016 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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