# $NP$ is not in $P(n^k)$ for any fixed $k \geq 1$

I encountered this problem which asks to show that for any fixed $$k \geq 1$$, $$NP$$ is not contained in $$P(n^k)$$...

As an attempt, I thought of using the time hierarchy theorem which says that there exists a language in $$P(n^{k+1})$$ which is not decided in $$P(n^k)$$ given that $$n^k \in o(n^{k+1})$$... Since the space of polynomial verifiers in $$NP$$ is the union of all polynomials of $$n$$, using the time hierarchy theorem, this means that there exists a problem in $$NP$$ that accepts instances only if the accepting branch operates in time $$P(n^{k+1})$$, and so $$NP$$ could not be contained in $$P(n^k)$$...

But is this correct ? I only assumed that such a problem exists in $$NP$$ (i.e. which accepts in nondeterministic time $$P(n^{k+1})$$ due to the time hierarchy theorem, but I have not really been able to construct a concrete problem...

• Since the space of polynomial verifiers ... etc.: just say that $P \subseteq NP$. Therefore, $T(n^k) \subsetneq T(n^{k+1}) \subseteq P \subseteq NP$. – Dmitry Jul 18 '20 at 12:01