2020-05-04
((resource:image0 (17).jpeg|Resource Description for image0 (17).jpeg))
P is a subset of TIME(2^n) with theorem.
TIME(2^n) is a proper subset of TIME(2^2n).
TIME(2^2n) is a proper subset of EXP(P).
This is a proper subset of EXP.
P is a subset of TIME(2^n) with theorem.
TIME(2^n) is a proper subset of TIME(2^2n).
TIME(2^2n) is a proper subset of EXP(P).
This is a proper subset of EXP.
P ⊆ TIME(2^n)
By the Hierarchy Theorem, TIME(2^n)⊊TIME((n^2)*(2^n)^2),
Then TIME(n^2*(2^n)^2) also ⊆ EXP
Following these, P ⊊ TIME(2^n), TIME(2^n) ⊊TIME((n^2)*(2^n)^2), TIME(n^2*(2^n)^2) also ⊆ EXP
so we can conclude P ⊊ EXP
(Edited: 2020-05-04) P ⊆ TIME(2^n)
By the Hierarchy Theorem, TIME(2^n)⊊TIME((n^2)*(2^n)^2),
Then TIME(n^2*(2^n)^2) also ⊆ EXP
Following these, P ⊊ TIME(2^n), TIME(2^n) ⊊TIME((n^2)*(2^n)^2), TIME(n^2*(2^n)^2) also ⊆ EXP
so we can conclude P ⊊ EXP
P is in TIME 2^n which is also in TIME (2^(3n)).
(2^(3n)) grows slower than 2 ^(n^k) which is in EXP
P is in TIME 2^n which is also in TIME (2^(3n)).
(2^(3n)) grows slower than 2 ^(n^k) which is in EXP
P ⊆ TIME(2^n); TIME(2^n) ⊊ TIME((n^2)*(2^n)^2). For any k > 0, 2^n is faster than n^k. TIME((n^2)*(2^n)^2) ⊊ EXP. Therefore, P ⊊ EXP
P ⊆ TIME(2^n); TIME(2^n) ⊊ TIME((n^2)*(2^n)^2). For any k > 0, 2^n is faster than n^k. TIME((n^2)*(2^n)^2) ⊊ EXP. Therefore, P ⊊ EXP
P is time 2^n this is also in time (2^(3n)), also (2^(3n)) grows slower than 2 ^(n^k) which is also in EXP
P is time 2^n this is also in time (2^(3n)), also (2^(3n)) grows slower than 2 ^(n^k) which is also in EXP
Let k be any constant c
P = UcTIME(n^c)
EXP = UcTIME(2^n^c)
UcTIME(n^c) ⊊ UcTIME(2^n^c)
QED P ⊊ EXP
(Edited: 2020-05-04) Let k be any constant c
P = UcTIME(n^c)
EXP = UcTIME(2^n^c)
UcTIME(n^c) ⊊ UcTIME(2^n^c)
QED P ⊊ EXP
P is a subset of TIME(2^n)
using time hierarchy theorem,
TIME(2^n) is a subset not equal to TIME((2^n)^2), but
TIME((2^n)^2) is a subset of EXP P is a subset not equal to EXP
P is a subset of TIME(2^n)
using time hierarchy theorem,
TIME(2^n) is a subset not equal to TIME((2^n)^2), but
TIME((2^n)^2) is a subset of EXP
P is a subset not equal to EXP
(c) 2024 Yioop - PHP Search Engine