patternMinor
NP $\subsetneq$ EXP?
Viewed 0 times
expsubsetneqstackoverflow
Problem
I think I heard in somewhere that it has been proven that $\mathsf{NP}$ is strictly contained in $\mathsf{EXP}$, that is $\mathsf{NP} \subsetneq \mathsf{EXP}$. Is this right? Wikipedia and book resources do not seem to bring me an answer..
I just found a post similar to this, but I am not sure whether $\mathsf{NP}$ is strictly contained in $\mathsf{EXP}$.
I just found a post similar to this, but I am not sure whether $\mathsf{NP}$ is strictly contained in $\mathsf{EXP}$.
Solution
Strictly contained means $\subsetneq$, i.e. it is the definition, it is not a result. So what you are saying is
$$\mathsf{NP} \subsetneq \mathsf{ExpTime} \implies \mathsf{NP} \subsetneq \mathsf{ExpTime}$$
which is trivially true.
If you are asking if $\mathsf{NP}\subsetneq \mathsf{ExpTime} $ then the answer is: it is unknown.
You may want to check the Wikipedia article about Exponential Time Hypothesis which many experts believe is true.
$$\mathsf{NP} \subsetneq \mathsf{ExpTime} \implies \mathsf{NP} \subsetneq \mathsf{ExpTime}$$
which is trivially true.
If you are asking if $\mathsf{NP}\subsetneq \mathsf{ExpTime} $ then the answer is: it is unknown.
You may want to check the Wikipedia article about Exponential Time Hypothesis which many experts believe is true.
Context
StackExchange Computer Science Q#1853, answer score: 5
Revisions (0)
No revisions yet.