-2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Yes $-$ our lives wouldn't be better. $\endgroup$ – TonyK Dec 29 '15 at 19:51
  • $\begingroup$ What are the consequences? One for sure is that RSA encryption would be in NP. $\endgroup$ – mathacka Dec 29 '15 at 19:52
  • 1
    $\begingroup$ A constructive proof that P=NP means there is no digital security. Do I need to explain that that's not a good thing? $\endgroup$ – djechlin Dec 29 '15 at 20:20
  • 1
    $\begingroup$ @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). $\endgroup$ – Noah Schweber Dec 29 '15 at 20:30
  • $\begingroup$ @NoahSchweber why's that? seems odd to me that we could prove any proof is constructive. $\endgroup$ – djechlin Dec 29 '15 at 20:31
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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/… $\endgroup$ – Dan Brumleve Dec 29 '15 at 20:31
  • $\begingroup$ @DanBrumleve Indeed, and see my comments to djechlin above. $\endgroup$ – Noah Schweber Dec 29 '15 at 20:38
  • $\begingroup$ 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 . . . $\endgroup$ – Noah Schweber Dec 29 '15 at 21:13
  • $\begingroup$ 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? $\endgroup$ – Dan Brumleve Dec 29 '15 at 21:21
  • $\begingroup$ Hm, this does seem to use $NP=coNP$. I remember this being fixable, though . . . $\endgroup$ – Noah Schweber Dec 29 '15 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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