3 ms·
I'm struggling to see how a proof of P=NP really makes any difference, though- other than psychologically, in the minds of people working on solving problems.
by dekhn 3y ago
I'm struggling to see how a proof of P=NP really makes any difference, though- other than psychologically, in the minds of people working on solving problems.
It doesn't have any real practical use for people actually building empirically faster implementations of useful algorithms (like SAT, as you mention).
I should have been clearer in stating my premise: it appears that determining that P=NP itself would have no real direct impact on any existing real-life problems; in nearly all cases, "faster algorithms that impact life" come from a combination of theoretical computer science discoveries combined with engineering (partly CS engineering, partly hardware engineering).
I'd love to find a real counterexample, IE, something in material science, or logistics/optimization, that would make a difference to the world economy. I see CS folks get really excited about this but often times as I poke and pull on the facts, I find that the more theoretical computational complexity gets, the less impact it has on daily activities.
- tsimionescu 3y agoI think I see where you're coming from, at least somewhat. Any revolution would come from finding a fast algorithm for an interesting problem, which would also happen to prove P=NP, but that wouldn't be the important part. The algorithm itself would be.