World's most popular travel blog for travel bloggers.

[Solved]: How to prove 2-EXP != EXP

, , No Comments
Problem Detail: 

I am guessing that this is correct for 3-EXP, 4-EXP etc...

Basically I should find a problem in 2-EXP that is not in EXP. Any examples ?

Asked By : Michael

Answered By : Vor

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))$

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback