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$ Commented 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$ Commented May 5, 2016 at 17:58
  • 1
    $\begingroup$ @EmilJeřábek : ​ ​ ​ In fact, that can easily be strengthened to ​ NE/poly = coNE/poly . ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented May 5, 2016 at 19:30
  • $\begingroup$ Of course. I stated it for NEXP as that’s what the question is about. $\endgroup$ Commented May 5, 2016 at 20:26
  • $\begingroup$ @RickyDemer Could $\mathsf{NP/poly}=\mathsf{coNP/poly}$ be true? Would this have any implications? $\endgroup$
    – Turbo
    Commented Oct 23, 2016 at 21:54

Your Answer

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

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