[rrjjww]

As someone who is only vaguely familiar with the P = NP problem, can someone explain to me if proving P=NP automatically solves the numerous problems that can then be “quickly computed” or does it simply prove there is an existence of an algorithm for each problem?

To rephrase if this is not the case - what value does solving P = NP provide?

[jcranmer]

There are roughly four possibilities for P = NP:

* P != NP. In practical terms, nothing changes.

* Nonconstructive case. The resulting algorithm looks something like some primality test algorithms (which I'll describe): essentially, if a number n is composite, then there is some (X + a)^n = X^n + a in Z/nZ (X is a polynomial here). If you test "enough" a's, then you can prove whether n is prime or composite. A nonconstructive case would mean we have a proof that you only need to test poly(lg n) a's to confirm truth, without necessarily telling which a's you have to test. In this world, there is no practical change to problems--the proof doesn't yield an effective algorithm to actually solve any NP-complete problem.

* Combinatorial algorithm for an NP-complete problem. The good example here is what has been done to prove L = SL. The result is "technically" in L, but the factors in the algorithm run very quickly into "more than the number of atoms in the universe" phase. The goal is to find a memory-less algorithm (can't use a visit stack) that can prove a path between two points in an undirected graph, and it turns out that you can transform the graph into another one that will guarantee that you will visit every node in a certain amount of time. The found result has a new graph that replaces every node with more nodes than exist atoms in the universe, so it technically meets the requirements but is completely and totally impractical. Sometimes people handwave this possibility by saying that once an algorithm is found, people will find better results, but this result hasn't been improved on in close to two decades.

* "Simple" algorithm for an NP-complete problem. This is the result that really, really changes things. Once you get a simple algorithm for one NP-complete problem, you can generally find analogous ways to get simple algorithms for other NP-complete problems. However, the research done to date does suggest that this is perhaps the least likely solution: looking at the "hard" instances of SAT problems, it does seem that there is a certain complexity that is at best reducible via some sort of combinatorical nightmare construction rather than the kinds of decompositions that yields "simple" algorithms.

[btdmaster]

It's only required to prove an algorithm that solves an NP-complete problem exists, not find it.

Even if that algorithm exists and was found, it could be that such an algorithm is O(n^123456789), which would not break RSA in any practical sense, though it would be mathematically asymptotically faster than O(2^n).

[erik]

If P == NP, then it could be possible that a proof would show that an algorithm must exist without providing such an algorithm. But that approach wouldn't be necessary, actually showing an algorithm would of course also be a proof.

> To rephrase if this is not the case - what value does solving P = NP provide?

P vs NP is a question of enormous practical interest. But it's also a very interesting question of pure mathematics. A proof that P != NP, or a proof of P == NP that didn't provide an algorithm would still be a huge deal in the math and computer science world.

[bodhiandphysics]

Think about cryptography for a second…. In cryptography you need a problem that if you know the key is fast to decode but if you don’t is really slow… like you would have to search all the possibilities one by one. Such problems are (basically…) called NP. P are all the algorithms that are fast on computers. If P = NP than any problem you could use for cryptography could be decoded fast

[Dylan16807]

P does not mean fast.

P means you don't have to try every single possible answer.

But lots of algorithms fit that description while still being impractically slow. Keys might still be uncrackable.

[goodgoblin]

It's been a little while - but I think it's because NP problems can be converted into each other, so if you can solve one of them in P you can solve all of them in P.