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

  • 2
    $\begingroup$ 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$. $\endgroup$ – Dmitry Jul 18 '20 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.