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:
- How is the time hierarchy theorem (or anything else) used to prove that P≠EXPTIME?
- 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?
Asked By : rb612
Answered By : David Richerby
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.
Correct: we conjecture that P$\,\neq\,$NP and NP$\,\neq\,$EXP but we don't have a proof of either of those things.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/58116
0 comments:
Post a Comment
Let us know your responses and feedback