# Is NEXP = co-NEXP?

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?

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.

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