5 ms·

The actual result of "P =/= NP" wouldn't actually be very interesting or informative - after all, we're all pretty sure of that anyway. What would be very inte

The actual result of "P =/= NP" wouldn't actually be very interesting or informative - after all, we're all pretty sure of that anyway. What would be very interesting - and likely give pretty deep insights into the very nature of computation - would be how exactly they proved it.

drostie 8y ago
Right. The important thing about the Clay Mathematics Millenium Prize is that it is a set of well-chosen SMART-ish goals. They want to incentivize work on really hard fields of mathematics but they have tried to do this by choosing results that are each not too intimidating. The Navier-Stokes prize, for example, allows you to assume all of the nicest features of Navier-Stokes problems in practice -- basically all of the fluid flows are well below supersonic and are occurring in highly homogeneous, nice fluids -- and ask the most basic mathematical question: does a smooth solution to these equations always exist? That question by itself is not so important, but it's specific and measurable. But it's a bit of a "reach" -- you would have to have some cutting insight about turbulence in order to answer this question one way or the other. That cutting insight is what they're trying to incentivize. P vs NP is the same: if solutions to a problem are easy to check, is there always some better way to analyze the mechanics of the checker to make those solutions easy to find, so that we aren't stuck with brute-forcing it? Whether the answer goes one way or the other, the point is that solving the problem would have to provide some insight to the effect of "here is a periodic table of elements for all of the 'easy' algorithms -- and here are the properties of all the 'molecules' made by combining those building blocks." And only once someone advances our understanding with those cutting insights can we say "yes we can always reach into the verification mechanism to understand it well enough to build a better-than-brute-force algorithm" or "no, here is such a thing that algorithms cannot do, it's not just that I am not smart enough to find a way for them to do this -- they are fundamentally incapable of doing it faster."

drostie 8y ago

Right. The important thing about the Clay Mathematics Millenium Prize is that it is a set of well-chosen SMART-ish goals. They want to incentivize work on really hard fields of mathematics but they have tried to do this by choosing results that are each not too intimidating. The Navier-Stokes prize, for example, allows you to assume all of the nicest features of Navier-Stokes problems in practice -- basically all of the fluid flows are well below supersonic and are occurring in highly homogeneous, nice fluids -- and ask the most basic mathematical question: does a smooth solution to these equations always exist? That question by itself is not so important, but it's specific and measurable. But it's a bit of a "reach" -- you would have to have some cutting insight about turbulence in order to answer this question one way or the other. That cutting insight is what they're trying to incentivize. P vs NP is the same: if solutions to a problem are easy to check, is there always some better way to analyze the mechanics of the checker to make those solutions easy to find, so that we aren't stuck with brute-forcing it? Whether the answer goes one way or the other, the point is that solving the problem would have to provide some insight to the effect of "here is a periodic table of elements for all of the 'easy' algorithms -- and here are the properties of all the 'molecules' made by combining those building blocks." And only once someone advances our understanding with those cutting insights can we say "yes we can always reach into the verification mechanism to understand it well enough to build a better-than-brute-force algorithm" or "no, here is such a thing that algorithms cannot do, it's not just that I am not smart enough to find a way for them to do this -- they are fundamentally incapable of doing it faster."