Please post your solutions to the Apr 29 In-Class Exercise to this thread.

Best,

Chris

2^n grows faster than polynomial time (n^k), where k>0. We can have (2^n)^3, which is 2^(3n). 2^(3n) grows slower than 2^(n^k).

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 is a subset of TIME(2^n) TIME(2^n) is a subset not equal to TIME((n^2)(2^n)^2) TIME(n^2(2^n)^2) is a subset of EXP P is a subset not equal to EXP

P is in Time(2^n) which is also in TIME(2^(3n)). 2^(3n) grows slower than 2^(nk) when k = 2

P is in time 5^n and is also a subset of time 5^5n. When comparing 5^5n and 5^n, the former will grow faster than the latter for any given k > 0.

P ⊆ TIME(2^n)

TIME(2^n)TIME((n^2)*(2^n)^2)

TIME(n^2*(2^n)^2) ⊆ EXP

P EXP

P is a subset of TIME (2^n) Following time hierarchy theorem, TIME(2^n)TIME((2^n)^2) But, TIME((2^n)^2) ⊆ EXP P EXP