P is properly contained in DTIME(T'(n)).

102 Views Asked by At

There is a function T (which is not time-constructible, but is computable), such that $ P = DTIME(T(n)) \, . $ For every polynomial $p(n)$ , it holds that $p(n)=o(T(n))$. For every time-constructible function $T'$ such that $p(n)=o(T'(n))$ for every polynomial p, it also holds that $$T(n)logT(n)=o(T'(n))\,.$$

How does the above fact mean that

For every time-constructible function $T'$ such that $n^k=o(T'(n))\,.$ for every k,it holds that P is properly contained in $DTIME(T'(n))\,.$

1

There are 1 best solutions below

0
On

I'll give it a try, correct me if I am wrong. Recall that $P$ = $⋃$ DTIME($n^{k}$) and also $ 0\leq n^{k}\leq T'(n)$ where $T'$ is time constructible and $k\geq 1$. This means $n^{k} ⊆ T'(n)$ and similarly $P⊆DTIME(T'(n))$ from hierarchy theorem.