8
$\begingroup$

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?
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Albert Hendriks
    Jun 1, 2016 at 7:20
  • $\begingroup$ @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?" $\endgroup$
    – David Richerby
    Jun 1, 2016 at 16:16

1 Answer 1

Reset to default
6
$\begingroup$

  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.

$\endgroup$
4
  • $\begingroup$ Awesome! Now why doesn't the time hierarchy theorem hold for NP too? $\endgroup$
    – rb612
    Jun 1, 2016 at 16:19
  • $\begingroup$ @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). $\endgroup$
    – David Richerby
    Jun 1, 2016 at 16:26
  • $\begingroup$ ah, I was just thinking that a variation of the theorem would be something like harder problems exist as NP-complete because given a polynomial amount of time, there are harder problems that only nondeterministic turing machines could solve in the same amount of time as deterministic turing machines. But I guess the time hierarchy theorem can't be expanded this far? $\endgroup$
    – rb612
    Jun 1, 2016 at 16:40
  • $\begingroup$ @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.) $\endgroup$
    – David Richerby
    Jun 1, 2016 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.