3 ms·

Out of curiosity, if someone proved P to not equal NP, what kind of scope and effect would it bring to the world outside academia? P == NP would obviously be a

Out of curiosity, if someone proved P to not equal NP, what kind of scope and effect would it bring to the world outside academia? P == NP would obviously be a world-transforming proof

gear54rus 8y ago
as I understand it would have little effect since it's implicitly assumed to be that way, might be wrong though
- chupasaurus 8y ago
  RSA algorithm is based upon factorization, reverse problem for which is in NP. If a solution's difficulty is a low degree polinom (3 or lower, but I might be wrong) it could be used to get private keys from public ones in a matter of days.
  - nabla9 8y ago
    The proof itself would not give factorization algorithm. Even if P = NP, prime factorization can be very time consuming to solve. The prime factorization problem is in the NP class, but we don't know if it is NP-hard.
  - raverbashing 8y ago
    Factorization is not NP, it's "easier"
    - chupasaurus 8y ago
      It's definitely in the class, but it's undecided which subclass it belongs to.
d3ckard 8y ago
It would probably give us some new insight on what computation actually is. Our inability to formally proof class separation suggests we're missing something.
MrEldritch 8y ago
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."

Out of curiosity, if someone proved P to not equal NP, what kind of scope and effect would it bring to the world outside academia? P == NP would obviously be a world-transforming proof

gear54rus 8y ago

as I understand it would have little effect since it's implicitly assumed to be that way, might be wrong though

chupasaurus 8y ago
RSA algorithm is based upon factorization, reverse problem for which is in NP. If a solution's difficulty is a low degree polinom (3 or lower, but I might be wrong) it could be used to get private keys from public ones in a matter of days.
- nabla9 8y ago
  The proof itself would not give factorization algorithm. Even if P = NP, prime factorization can be very time consuming to solve. The prime factorization problem is in the NP class, but we don't know if it is NP-hard.
- raverbashing 8y ago
  Factorization is not NP, it's "easier"
  - chupasaurus 8y ago
    It's definitely in the class, but it's undecided which subclass it belongs to.

d3ckard 8y ago

It would probably give us some new insight on what computation actually is. Our inability to formally proof class separation suggests we're missing something.

MrEldritch 8y ago

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."