To rephrase if this is not the case - what value does solving P = NP provide?
To rephrase if this is not the case - what value does solving P = NP provide?
* 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.
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).
> 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.
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.