5 ms·

Are you kidding/trolling? The P=NP problem is FAR more fundamental, and if proven true, would basically be a proof that e.g. public key crypto can be broken (NO

Are you kidding/trolling? The P=NP problem is FAR more fundamental, and if proven true, would basically be a proof that e.g. public key crypto can be broken (NOT a description of how to though). Basically, it would be a proof that all the REALLY hard (combinatorial) problems out there, have a much simpler solution, if we were able to find it. EDIT: NS is used daily in engineering and gas/fluid modeling. We sort of “know it works”. The smoothness proof is “just” formalizing what practitioners assume is true (very coarsely said, no intention to diminish the result!) It’s a bit like the Collatz function IMO, empirical evidence isn’t proof, but we’ve got a huge amount of evidence for the behavior we’re trying to prove. I believe P vs NP is a different beast entirely. We don’t even know which way the answer should go.

eru 7d ago
> The P=NP problem is FAR more fundamental, Yes. > and if proven true, would basically be a proof that e.g. public key crypto can be broken (NOT a description of how to though). Well, only if the answer is that P=NP. > I believe P vs NP is a different beast entirely. We don’t even know which way the answer should go. Most people expect P < NP, and then crypto wouldn't be broken. P=NP would also break pseudo-random number generators, for pretty much the same reason as the rest of crypto. However Don Knuth is one example of an expert who thinks P = NP is plausible. Btw, we do know quite a lot about how a proof of P vs NP will _not_ look like. That is we are in the curious situation where we can prove that certain proof techniques won't work on this problem. Weirdly enough, we already have the optimal algorithm, we just can't prove its runtime. Ie we have an algorithm that runs in polynomial time on all NP hard problems, if P=NP. (But the constant factors are crazy.)

eru 7d ago

> The P=NP problem is FAR more fundamental, Yes. > and if proven true, would basically be a proof that e.g. public key crypto can be broken (NOT a description of how to though). Well, only if the answer is that P=NP. > I believe P vs NP is a different beast entirely. We don’t even know which way the answer should go. Most people expect P < NP, and then crypto wouldn't be broken. P=NP would also break pseudo-random number generators, for pretty much the same reason as the rest of crypto. However Don Knuth is one example of an expert who thinks P = NP is plausible. Btw, we do know quite a lot about how a proof of P vs NP will _not_ look like. That is we are in the curious situation where we can prove that certain proof techniques won't work on this problem. Weirdly enough, we already have the optimal algorithm, we just can't prove its runtime. Ie we have an algorithm that runs in polynomial time on all NP hard problems, if P=NP. (But the constant factors are crazy.)