Yioop - PHP Search Engine

Apr 29 In-Class Exercise Thread.

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

Best,

Chris

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

-- Apr 29 In-Class Exercise Thread

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

(Edited: 2020-04-29)

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

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

-- Apr 29 In-Class Exercise Thread

 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

(Edited: 2020-04-29)

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

-- Apr 29 In-Class Exercise Thread

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

-- Apr 29 In-Class Exercise Thread

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.

-- Apr 29 In-Class Exercise Thread

P ⊆ TIME(2^n)

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

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

P ⊊ EXP

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

-- Apr 29 In-Class Exercise Thread

(Edited: 2020-04-29)

((resource:Capture.PNG|Resource Description for Capture.PNG))

-- Apr 29 In-Class Exercise Thread

((resource:Screen Shot 2020-04-29 at 5.02.06 PM.png|Resource Description for Screen Shot 2020-04-29 at 5.02.06 PM.png))

-- Apr 29 In-Class Exercise Thread

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