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

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?

• Yes $-$ our lives wouldn't be better. – TonyK Dec 29 '15 at 19:51
• What are the consequences? One for sure is that RSA encryption would be in NP. – mathacka Dec 29 '15 at 19:52
• A constructive proof that P=NP means there is no digital security. Do I need to explain that that's not a good thing? – djechlin Dec 29 '15 at 20:20
• @djechlin A fun aside: any proof of P=NP would be constructive, in the following sense: there is a specific algorithm (perfectly concrete) that we can write down, that - if $P=NP$ - solves SAT in polytime. This is a fun silly exercise (it's not nearly as satisfying as we might hope . . . :P). – Noah Schweber Dec 29 '15 at 20:30
• @NoahSchweber why's that? seems odd to me that we could prove any proof is constructive. – djechlin Dec 29 '15 at 20:31

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

• Furthermore, a proof that $P=NP$ wouldn't necessarily make our lives better either. And I don't just mean that a SUBSET-SUM solver might involve huge constants or exponents, it might be entirely non-constructive. Note that if $P=NP$ we already have an algorithm that in polynomial time can find a solution if one exists, see en.wikipedia.org/wiki/… – Dan Brumleve Dec 29 '15 at 20:31
• @DanBrumleve Indeed, and see my comments to djechlin above. – Noah Schweber Dec 29 '15 at 20:38
• Note how absolutely godawful the runtime of the algorithm above is. In particular, since we need these pairs ordered the same way as $\mathbb{N}$, there's no way to prevent $(T_i, p_i)$ being the "right" pair with $p_i$ linear (say), but $p_{i-1}$ being a trillionth-degree polynomial (which would lead to a trillionth-degree runtime, roughly). Not to mention all the constants built in . . . – Noah Schweber Dec 29 '15 at 21:13
• Presumably the TMs output a witness, because we can check the answer in polytime. But what if we are given an unsolvable instance? It seems like we also need a "constuctive" proof of $NP=co-NP$ to make this work. I think this is essentially the same algorithm on wiki. Am I missing something here? – Dan Brumleve Dec 29 '15 at 21:21
• Hm, this does seem to use $NP=coNP$. I remember this being fixable, though . . . – Noah Schweber Dec 29 '15 at 21:23