3 ms·
Is the interesting part of P vs NP (since it seems very unlikely that P = NP) the mathematical machinery that would be required to prove that P != NP? Presumabl
by variadix 2y ago
Is the interesting part of P vs NP (since it seems very unlikely that P = NP) the mathematical machinery that would be required to prove that P != NP? Presumably doing so would require a way to determine a lower bound for _all_ possible algorithms that solve a particular problem.
- vasekrozhon 2y agoExactly! In theoretical computer science, we have a lot of experience coming up with new algorithms but no idea how to prove lower bounds. So I would say that new lower-bound technique is perhaps the most interesting thing we would learn from the proof of P!=NP. But, of course, P vs NP is clearly central to computer science and math for a bunch of other reasons, hopefully, our video provided some intuitions.