# How do we know for sure that EXPTIME ≠ P?

I'm a beginner in learning about computational complexity and this has stumped me. I've read that by the time hierarchy theorem, it's known that EXP-complete problems are not in P. (Wikipedia) It makes absolute sense intuitively that this is the case, as does P≠NP. From what I understand, the time hierarchy theorem states that given more time, a turing machine can solve harder problems.

I have 2 questions:

1. How is the time hierarchy theorem (or anything else) used to prove that P≠EXPTIME?
2. If we assume P=NP and NP=EXP, P=EXP and that contradicts P≠EXP. So one of those statements MUST be false. But we can only conjecture that both these are false, and can't prove it? Is that the case?
• P$\neq$EXPTIME because we know for sure that some problems really require exponential time (I don't know which), while P problem don't require that by definition. Because of that it is indeed true that either P$\neq$NP or NP$\neq$EXPTIME (or both), but we can't prove which. Jun 1 '16 at 7:20
• @AlbertHendriks The first part of the question is precisely how to use the time hierarchy theorem to prove that some problems require exponential time. So the first part of your comment is just re-stating the question, minus the "So how do you prove it?" Jun 1 '16 at 16:16

1. The time hierarchy theorem says that, for any reasonable function $f$, there are problems that can be decided in time $O(f(n))$ that cannot be decided in time, say, $O(f(n)/n)$. (There are various versions of the time hierarchy theorem. The one I've just quoted isn't standard but it's strong enough to prove what we need, here.) In particular, then, there are problems that can be solved in time $O(2^n)$ that cannot be solved in time $O(2^n/n)$ so, in particular, cannot be solved in time $O(n^k)$ for any $k$. These problems are in EXP but not in P.
2. Correct: we conjecture that P$\,\neq\,$NP and NP$\,\neq\,$EXP but we don't have a proof of either of those things.
• @rb612 I'm not sure exactly what you mean. There is a time hierarchy theorem for nondeterministic machines, which says that $\mathrm{NTime}[f(n)]\subsetneq \mathrm{NTime}[g(n)]$ when $f=o(g)$. But that doesn't allow you to separate P and NP because that requires comparing deterministic and nondeterministic machines, whereas the hierarchy theorems only allow us to compare det-det (e.g., P≠EXP) or nondet-nondet (e.g., NP≠NEXP). Jun 1 '16 at 16:26
• @rb612 The hierarchy theorems only allow comparing like with like. The difference between $\mathrm{Time}[f(n)]$ and $\mathrm{Ntime}[f(n)]$ isn't well-understood and P vs NP is just the most prominent example of that. (On the other hand, the relationship between $\mathrm{Space}[f(n)]$ and $\mathrm{NSpace}[f(n)]$ is much better understood.) Jun 1 '16 at 17:43