snippetModerate
How to prove 2-EXP != EXP
Viewed 0 times
proveexphow
Problem
I am guessing that this is correct for
Basically I should find a problem in
Any examples ?
3-EXP, 4-EXP etc...Basically I should find a problem in
2-EXP that is not in EXP.Any examples ?
Solution
It is a direct consequence of the time hierarchy theorem:
Time Hierarchy Theorem: if f and g are time-constructible functions and $f(n) \log f(n) =
o(g(n))$ (e.g. $f(n) = n^2, g(n) = n^3$), then $DTIME(f(n)) \subsetneq DTIME(g(n))$
Time Hierarchy Theorem: if f and g are time-constructible functions and $f(n) \log f(n) =
o(g(n))$ (e.g. $f(n) = n^2, g(n) = n^3$), then $DTIME(f(n)) \subsetneq DTIME(g(n))$
Context
StackExchange Computer Science Q#2422, answer score: 13
Revisions (0)
No revisions yet.