0
$\begingroup$

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}$.)

$\endgroup$
5
  • $\begingroup$ A yes or no answer (possibly with a reference) is likely sufficient for this question. $\endgroup$
    – kc9jud
    Commented Jan 22, 2023 at 23:25
  • 1
    $\begingroup$ 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$. $\endgroup$ Commented Jan 23, 2023 at 0:32
  • $\begingroup$ @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? $\endgroup$
    – kc9jud
    Commented Jan 23, 2023 at 18:13
  • $\begingroup$ 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}$" $\endgroup$ Commented Jan 23, 2023 at 22:49
  • $\begingroup$ Technically what you wrote was correct... if a language is not in $\mathsf{NP}$, it's definitely not in $\mathsf{P}$! $\endgroup$
    – kc9jud
    Commented Jan 24, 2023 at 7:54

1 Answer 1

0
$\begingroup$

If you look at the definition of NP, every problem in P is obviously in NP. P means “all instances can be solved in polynomial time”, NP means “instances with a yes answer and a useful hint can be solved in polynomial time”.

Since P is a subset of NP, P ≠ NP means some problems in NP cannot be solved in polynomial time. NP complete problems can by definition not be in P in that case.

Since the number of possible polynomial size hints is “only” exponential we can find answers to “yes” instance in exponential time. And if we can’t find an answer fast enough, then it must be “no”.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.