1
$\begingroup$

Is there a list of implications of $P=NP$?

Presumably, a proof of $P \ne NP$ will be by contradiction, for which a list of consequences of $P=NP$ would be useful.

Improve this question
$\endgroup$
2

3 Answers 3

Reset to default
1
$\begingroup$

If P=NP, then all of the NP problems can be solved deterministically in Polynomial time.

This is because the NP problems are all essentially the same problem, just stated in different terms.

As far as lists go -- many of the NP-Complete problems are enumerated here: https://en.wikipedia.org/wiki/List_of_NP-complete_problems

Further implications? Our cryptosystems break down, armchair philosophers argue about what it means, the world changes, and somebody gets a Fields medal or Turing award + a big hunk of cash, etc... but that's a tangent.

For example, one of the classic NP problems is clique. If you could solve clique with a polynomial time algorithm, this would prove that P=NP, and then you could also use your method for solving clique to solve all of the other problems on that wiki-list, as an implication.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ If P=NP then all NP problems can be solved deterministically in polynomial time because you've just said that they're in P and that's what P means. It has nothing to do with "the NP problems are essentially the same problem." It would make sense to say "If there is a deterministic polytime solution for any NP-compete problem, then P=NP because all problems in NP are essentially the same problem." $\endgroup$
    – David Richerby
    Jan 24, 2019 at 10:58
1
$\begingroup$

There wouldn't be a lot of practical implications. In practice, the question is not whether a problem can be solved in polynomial time, the question is whether it can be solved in a reasonable amount of time.

Let's say I can solve the Travelling Salesman problem for n cities in n^12 nanoseconds. So what? N=50 still takes thousands of years.

No fast algorithms for this problem are known. P=NP doesn't magically give us any fast algorithms.

Of course P = NP would affect a huge number of open problems in computer science, where certain problems are obviously in P, and obviously in NP but not known to be NP-complete, and it is unknown where exactly between P and NP they are - all these problems would be known to be in P. (See this question for example: Existence of NP problems with complexity intermediate between P and NP-hard )

And if a guaranteed polynomial time algorithm for checking primality hadn't been known, we would know that one exists (but that knowledge would have been no help whatsoever to find this algorithm).

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ "There wouldn't be a lot of practical implications." There might not be a lot of practical implications. It's possible that P=NP, that the proof is nonconstructive and the best algorithm for TSP runs in time $\Theta(n^{12})$. It's also possible that we prove that P=NP precisely by finding an $O(n\log n)$ algorithm for SAT or TSP or something like that. Without knowing why P=NP, we can't say what practical implications that would have. $\endgroup$
    – David Richerby
    Jan 24, 2019 at 10:54
-2
$\begingroup$

It also implies that some unsolvable problems may just be very hard. One of which being "which specific genes cause the phenomenon of consciousness" which could yet be solvable.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ No. P=NP would only have implications for which solvable problems can be solved efficiently. It wouldn't make unsolvable (undecidable) problems solvable: we know unconditionally that they can't be solved. $\endgroup$
    – David Richerby
    Jan 24, 2019 at 10:55

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