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

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.