Is there any significant consequence if P does not equal NP-complete?

Question

I hear a lot on these forums about how if P=NP-complete how our lives would be better, is there any significant consequence if we found P to be not equal to NP-Complete?

Answer 1

The problem is that $P\not=NP$ is roughly the "default" in terms of real-world applications. Currently we don't have an algorithm to solve NP-complete problems in polynomial time. Knowing "$P\not=NP$" would just reinforce that reality.

Now, this is a bit disingenuous - having a proof that $P\not=NP$ would almost certainly involve huge new ideas, which themselves would have important impacts - but the mere fact that "$P\not=NP$" wouldn't obviously lead to anything new in the "real world."

---

To avoid clogging the comment thread above, let me give an attempt at an explicit polytime SAT-solver (assuming P=NP) here. As Dan Brumleve shows below, this doesn't quite work.

Let $\{(T_i, p_i): i\in\mathbb{N}\}$ be a list of all pairs of the form (Turing machine, polynomial), ordered "reasonably" (there's some coding considerations here which I'm going to sweep under the rug). Now suppose I am given an instance $\sigma$ of SAT. I'll now run a potentially $(\vert\sigma\vert+2)$-stage procedure:

• Stage 0. Run $T_0(\sigma)$ for $p_0(\vert\sigma\vert)$-many steps. If it halts, check the answer (polytime!); if it's correct, halt and output it. If it's incorrect, or if it hasn't halted in time, move on to . . .

• Stage 1. Run $T_1(\sigma)$ for $p_1(\vert\sigma\vert)$-many steps. If it halts, check the answer (polytime!); if it's correct, halt and output it. If it's incorrect, or if it hasn't halted in time, move on to . . .

. . .

• Stage $\vert\sigma\vert$. Run $T_{\vert\sigma\vert}(\sigma)$ for $p_{\vert\sigma\vert}(\vert\sigma\vert)$-many steps. If it halts, check the answer (polytime!); if it's correct, halt and output it. If it's incorrect, or if it hasn't halted in that time, EXIT THIS LOOP . . .

• Stage $\vert\sigma\vert+1$. . . . And just solve $\sigma$ by brute force.

Now if $P=NP$, then there's some pair $(T_i, p_i)$ such that $T_i$ solves SAT in $p_i$ time. Then it's easy to check that for $\sigma$ an instance of SAT, $T(\sigma)$ solves $\sigma$ in time roughly $$\sum_{j\le i}p_j(\vert\sigma\vert).$$

(In particular, if $P=NP$ then the "brute force" option is taken on only finitely many instances.)