0

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?

jaysonpowers
  • 475
  • 1
    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. – jaysonpowers Dec 29 '15 at 19:52
  • 1
    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
  • 1
    @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
  • Noah Schweber, can you explain that further? It sounds like you're talking about the same algorithm I linked in my other comment, but even if $P=NP$ that algorithm won't find the negative cases in polynomial time. I don't see how a proof of $P=NP$ necessarily gives us a way to patch that up. – Dan Brumleve Dec 29 '15 at 20:40
  • @DanBrumleve See the edit to my answer. – Noah Schweber Dec 29 '15 at 21:06
  • @djechlin See the edit to my answer. – Noah Schweber Dec 29 '15 at 21:06
  • 1
    Why do people feel they can downvote a valid question? – jaysonpowers Jul 18 '20 at 13:02

1 Answers1

4

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

Noah Schweber
  • 245,398
  • 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 https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms – 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
  • Note that wiki calls it a "semi-algorithm". – Dan Brumleve Dec 29 '15 at 21:23
  • Another fun fact that I remember working out while studying this is that, if you set up the parameters correctly (spend $2^{-i}$ fraction of the time running TM #i in parallel checking answers as they halt, no need for for the $p_i$), then this is the best semi-algorithm for SAT, up to some log factors maybe and of course a huge constant, but you can't beat that exponent. And it's the best in the same sense even when $P \ne NP$! – Dan Brumleve Dec 29 '15 at 21:43
  • (I should probably clarify that I don't really mean parallel, I mean increment a counter in a loop, let $i$ be the exponent of the largest power of $2$ dividing the counter, then run one step of $T_i$.) – Dan Brumleve Dec 29 '15 at 21:53
  • ... and I realize now that for it to be the "best" we need a computational model where the above loop iterates in constant time or close to it, which a TM is not, but I think it works to create a SAT solver on a RAM for example that is as fast (up to log factors and constants) as the fastest TM SAT solver. I'll have to stop soapboxing and mull this over some more. – Dan Brumleve Dec 30 '15 at 00:13