HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

NP $\subsetneq$ EXP?

Submitted by: @import:stackexchange-cs··
0
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}$.

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.

Context

StackExchange Computer Science Q#1853, answer score: 5

Revisions (0)

No revisions yet.