3 ms·
Oh it would change a lot. It would be an enormous psychological boost for everyone to find a practical algorithm. In any case, I think it's better to read PP a
by js8 2mo ago
Oh it would change a lot. It would be an enormous psychological boost for everyone to find a practical algorithm.
In any case, I think it's better to read PP as somebody would find a practical, albeit incomprehensible, algorithm for solving NP complete problems.
Although I probably disagree with PP, because even a candidate algorithm that mysteriously works without proof would have practical value, so this case is not predicated on proving.
I think a better example of genuinely practical but rather uninteresting (YMMV) mathematical proofs are proofs of convergence of numerical methods, FEM for example. (I have been through it in school, it was a torture.)
- enriquto 2mo ago> a practical, albeit incomprehensible, algorithm for solving NP complete problems. It would not not necessarily be practical, even if it ran in polynomial time. It may have cost O(n^c), with a totally out of order exponent like c=A(5,5) or whatever.
- js8 2mo agoI know, the goal was to strongman the argument.
- aleph_minus_one 2mo ago> > If a magic oracle tells you p=np, that's useless. How would that change anything? > Oh it would change a lot. It would be an enormous psychological boost for everyone to find a practical algorithm. OK, I tell you that P=NP, and that I am a magic oracle. So, you have you psychological boost for finding a practical algorithm for free. :-)
- js8 2mo agoKinda pointless, because a) I am already convinced that P=NP b) You have to convince many other people as well (that you're a magic oracle), because for the effect to work, lot of people would have to work on the problem (or at least spend tokens) Nevertheless, a plausible magic oracle (such as Lean-verified proof, even if non-constructive and incomprehensible for humans) would convince many to take a 2nd look.