0
$\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$
9
  • 1
    $\begingroup$ Yes $-$ our lives wouldn't be better. $\endgroup$
    – TonyK
    Dec 29, 2015 at 19:51
  • $\begingroup$ What are the consequences? One for sure is that RSA encryption would be in NP. $\endgroup$
    – jaysonpowers
    Dec 29, 2015 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, 2015 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, 2015 at 20:30
  • 1
    $\begingroup$ Why do people feel they can downvote a valid question? $\endgroup$
    – jaysonpowers
    Jul 18, 2020 at 13:02

1 Answer 1

Reset to default
4
$\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$
9
  • $\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, 2015 at 20:31
  • $\begingroup$ @DanBrumleve Indeed, and see my comments to djechlin above. $\endgroup$
    – Noah Schweber
    Dec 29, 2015 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, 2015 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, 2015 at 21:21
  • $\begingroup$ Hm, this does seem to use $NP=coNP$. I remember this being fixable, though . . . $\endgroup$
    – Noah Schweber
    Dec 29, 2015 at 21:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .