# Time complexity of $\mathsf{NP}$ problem under assumption of $\mathsf{P} \neq \mathsf{NP}$

A simple question, but I can't find an answer in quite the form I'm looking for:

Assume $$\mathsf{P} \neq \mathsf{NP}$$, and thus $$\mathsf{P} \subsetneq \mathsf{NP}$$. If we have $$L \in \mathsf{NP}$$ and $$L \notin \mathsf{P}$$, does that imply that there is no algorithm for $$L$$ which runs in $$O(n^k)$$ steps for all inputs of size $$n$$ (for any fixed value $$k\in\mathbb{N}$$)? I.e., there is no polynomial-time algorithm for $$L$$?

From this answer, that would imply that the time complexity of an optimal algorithm for a problem in $$\mathsf{NP}$$ (but not in $$\mathsf{P}$$) is bounded such that must run in between $$O(n^k)$$ and $$O(2^{p(n)})$$ time, correct? (Here we use that $$\mathsf{NP} \subseteq \mathsf{EXPTIME}$$.)

• A yes or no answer (possibly with a reference) is likely sufficient for this question. Commented Jan 22, 2023 at 23:25
• A language is by definition in ${\bf P}$ if and only if there exists a TM that decides $L$ in $O(n^k)$ time for fixed $k$. Equivalently, if a language is not in ${\bf NP}$, then no TM can decide it in $O(n^k)$ time for fixed $k$. The fact that your $L\in {\bf NP}$ is irrelevant. $L\not\in {\bf P }$ immediately implies that there is no algorithm for $L$ which runs in $O(n^k)$ time for constant $k$. Commented Jan 23, 2023 at 0:32
• @AspiringMat Right, I think the only reason why $L\in\mathsf{NP}$ is relevant is if you want the upper bound as well as the lower bound? Commented Jan 23, 2023 at 18:13
• Yes, also, a typo in what I wrote above: "Equivalently, if a language is not in ${\bf NP}$" should be "Equivalently, if a language is not in ${\bf P}$" Commented Jan 23, 2023 at 22:49
• Technically what you wrote was correct... if a language is not in $\mathsf{NP}$, it's definitely not in $\mathsf{P}$! Commented Jan 24, 2023 at 7:54