patternMinor
Is NEXP = co-NEXP?
Viewed 0 times
nexpstackoverflowprogramming
Problem
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?
$$\mathsf{NEXP}=\mathsf{Co{-}NEXP}?$$
Is it known whether these two classes are equal?
Solution
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.
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.
Context
StackExchange Computer Science Q#57082, answer score: 8
Revisions (0)
No revisions yet.