This is IMO, by far, the most important problem of computer science. I often wonder whether I will live long enough to see it settled one way or the other. In any case, definitely recommended reading.
But the techniques used would likely be insightful. Particularly with proving cryptographic protocols beyond "we had a contest & damn are these bits ever uncorrelated"
Or obviously even if the proof does show you how to do it but the exponent is some insanely large number (see some of Scott Aaronson's other articles about "busy beaver numbers"), then that does not change anything practically either.
Also, finding such algorithms should significantly expand our capabilities by expanding our understanding.
Let me give an example where such a case exists. In 2005, a paper came out finding an algorithm for determining undirected graph connectivity in log space, which means you can't keep an unbounded stack of nodes that you have visited (as the trivial depth-first or breadth-first search algorithms do). This algorithm relies on converting the input graph using an "expander graph," basically replacing every node with an instance of a graph. When I computed how large an expander graph had to be, I found that the smallest one was ... 3^65536. It's still a constant factor, but it's larger than the number of atoms in the universe. This kind of constant factor isn't unusual for combinatorics problems (this is the same kind of space where Graham's number comes up).
My suspicion is that if P=NP, it's likely to be so only via this kind of crazy combinatorial input, which is to say, the P algorithm is completely impractical.
Outside of combinatorial algorithms, there are several other cases where the asymptotically faster algorithms are generally disfavored due to practical concerns: primality testing (AKP is a P algorithm, but slower in practice); matrix multiplication (we keep finding better exponents, but the dominant algorithm remains Strassen, and even then, that's only going to be used for distributed matrix multiplication). You mention linear programming, but my understanding is that interior point methods are generally preferred in modern implementations over simplex methods, the former being polynomial and the latter exponential (although very often polynomial in practice--another great example of typical case being far faster than worst case).
A proof of P!=NP would tell us two things. First, that there's something inherently different about NP-complete problems, and the proof would tell us exactly what.
Second, it would tell us how to figure that out, inevitably with an entirely new toolset for classifying problems. It would reverberate all over the computational complexity space and probably even give us new ideas for number theory.
The way I see it NP problems require exponential time by default. The reason some of them can be solved in polynomial time is because those problems contain some special structure that allows you to short-circuit the general solution with some kind of "trick".
Then P vs. NP boils down to does there exist a "general trick". In other words do all NP problems contain structure that can be exploited to short-circuit the calculation or not.
I do agree that actually proving that P != NP seems like it would require discovering some as yet unknown structure behind virtually all of mathematics, simply because the hypothetical "general trick" could be hidden in just about any mathematical structure we know about (or even in one we haven't discovered yet).
And we can strengthen this statement a bit, to really hammer home the intuition of why P=NP would be such a radical discovery.
"Simulating an arbitrary non-deterministic Turing machine for K steps" is itself an NP-complete problem, which would be solvable by a polynomial algorithm if P=NP. In other words, it's not just that all NP problems would have some structure that a sufficiently clever programmer could exploit; it's that there would exist a single algorithm that could automatically discover and exploit such structure in any NP problem.
To which he replies,
>>to make a sweeping statement like P ̸= NP, about what polynomial-time algorithms can't do, will require an unprecedented understanding of what they can do. This will almost certainly entail the discovery of many new polynomial-time algorithms, some of which could have practical relevance. In Section 6, we’ll see much more subtle examples of the “duality” between algorithms and impossibility proofs, with progress on each informing the other.
That's what we have, but it's not really comforting.
Now if you think what it'd mean to proove that e.g. a public key crypto system is secure, it almost implies that you'd need to proove p!=np before that. I.e. prooving p!=np would not proove that cryptography is secure, but it may be the first step and the understanding gained from prooving p!=np may mean that there's a much better understanding of complexity in general, which will help.
https://cs.stackexchange.com/questions/6650/how-can-p-np-enh...
It can be reduced already, but then 3-sat can be solved in P time
For example, you can assume part of the plaintext (like a header in transmission) and solve an equation (which can be restated as a SAT instance) that yields you a key assuming certain cryptographic algorithm was used. So pretty much all cryptography relies on P!=NP.
But don't worry, if that happens the world would be so different there might no longer be a need for cryptography.
https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...
https://en.wikipedia.org/wiki/NP-intermediate
Under the assumption that we understand P and NP a heck of a lot more if we were able to proof their distinctness, this hierarchy could possibly be used for actually USEFUL proof of work in crypto currencies, by choosing problems with exactly the right difficulty from a problem domain like protein folding.