-- Apr 29 In-Class Exercise Thread
P time is contained in TIME(2^n) b/c 2^n grows faster than any n^k
We know from the time hierarchy theorem that TIME(2^n) is contained in TIME(2^{3n})
TIME(2^{3n}) is contained in TIME(2^{n^2}), which is contained in EXP where k = 2
P time is contained in TIME(2^n) b/c 2^n grows faster than any n^k
We know from the time hierarchy theorem that TIME(2^n) is contained in TIME(2^{3n})
TIME(2^{3n}) is contained in TIME(2^{n^2}), which is contained in EXP where k = 2