If you want to make money online : Register now

[Solved]: Is NEXP = co-NEXP?

, , No Comments
Problem Detail: 

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?

Asked By : lukas.coenig

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57082

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback