-- Apr 29 In-Class Exercise Thread

((resource:Skärmavbild 2020-04-30 kl. 10.38.50.png|Resource Description for Skärmavbild 2020-04-30 kl. 10.38.50.png))

-- Apr 29 In-Class Exercise Thread

P = subset of Time 2^n with theorem, TIMe2^n is a proper subset of time2^2n but time2^2n is a proper subset of EXP P which is a proper subset of EXP

-- Apr 29 In-Class Exercise Thread

* As Professor Pollett says from around the 44:40 mark to the 45:15 mark of 24 Apr 29 Hierarchy Theorems, co-re sets, Reductions[Video], "We want to choose an f... which contains this class P, such that, say, f^3... is still contained within EXP." * I assume the f we choose should contain the class P because we want to show '''all''' of P is contained in EXP. * Let us pick f(n) = 2^n. Because f(n) = 2^n is slower than, or faster growing than, every function n^k in P, TIME(f(n) = 2^n) contains the entire class P. * From the deterministic time hierarchy theorem, "If f(n)≥n is a proper complexity function, then the class TIME(f(n)) is strictly contained in TIME(f(2n+1)^3)." * That is, if our function, f(n) = 2^n ">= n is a proper complexity function", which it is, "then the class TIME(f(n)) is strictly contained in TIME(f(2n+1)^3)." * f((2n+1)^3) = 2^((2n+1)^3) = 2^((4n^2 + 4n + 1)(2n + 1)) = 2^(8n^3 + 8n^2 + 2n + 4n^2 + 4n + 1) = 2^(8n^3 + 12n^2 + 6n + 1). * So, from the deterministic time hierarchy theorem, the class TIME(f(n)=2^n), which we know contains all of P, is strictly contained in TIME(f(2n+1)^3=2^(8n^3 + 12n^2 + 6n + 1)). * Since EXP:=∪kTIME(2^n^k), EXP includes TIME(f(2n+1)^3=2^(8n^3 + 12n^2 + 6n + 1)), so the class TIME(f(n)=2^n) is strictly contained in EXP. * The class TIME(f(n)=2^n) contains all of P and, by the deterministic time hierarchy theorem, is strictly contained in EXP:=∪kTIME(2^n^k). * Thus, P⊊EXP.

-- Apr 29 In-Class Exercise Thread

P is a subset of TIME (3^n). By the THT, TIME(2^n)⊊TIME((3^n)^2). However, TIME((3^n)^2) ⊆ EXP, meaning P ⊊ EXP

-- Apr 29 In-Class Exercise Thread

Because P is a subset of TIME(2^n) and that the time hierarchy theorem also gives that TIME(2^n) is a subset but not equal to TIME((2^n)^2), P is not a subset of EXP.

-- Apr 29 In-Class Exercise Thread

((resource:WechatIMG1591.png|Resource Description for WechatIMG1591.png))

-- Apr 29 In-Class Exercise Thread

Since P is the subset of TIME 2^n. By the time hierarchy theory, TIME2^n is the subset of TIME n^2 * (2^n)^2 equals to TIME 2^3n. However, 2^3n is slower than 2^(n^2). Therefore, P is not a subset of EXP.

-- Apr 29 In-Class Exercise Thread

P is a subset of time (2^n) according to the time hierarchy theorem, we know TIME(2^{3n}) grows slower than 2^(nk) when k = 2 so we knowp is a subset of EXP

-- Apr 29 In-Class Exercise Thread

P = subset of Time 2^n according to time hierarchy theorem, We know TIME(2^n) is the subset of TIME n^2 * (2^n)^2 which equals to TIME 2^3n. However, 2^3n is slower than 2^(n^2). Therefore, P is not a subset of EXP

-- Apr 29 In-Class Exercise Thread

P ⊆ TIME(2^n) From the Hierarchy Theorem TIME(2^n)⊊TIME((n^2)*(2^n)^2), but TIME(n^2*(2^n)^2) ⊆ EXP which shows P ⊊ EXP