4 ms·

Forgive my ignorance, but what would they be - the complete implosion of all forms of known security, or something else? This is a bit beyond my ken :)

snarf21 5y ago
Among other things, mostly encryption. Most of our current methods depends on P != NP. So no need for 0 days if you can just read at encrypted data as if it wasn't.
- Dylan16807 5y ago
  > Most of our current methods depends on P != NP. Not really. They depend on guessing being slow. P, just P, can do slow. P can be bigger than the universe even with low values of n.
kingaillas 5y ago
Well for one, the safety of encryption rests on certain problems being intractable. (In a theoretical sense; there are always implementation bugs that destroy security). If P=NP, then those previously thought to be intractable problems, are actually tractable. And the foundation of a lot of security-related engineering collapses.
- nafey 5y ago
  Is proving P = NP equivalent to knowing how any intractable problem can be solved? Is it possible for P=NP and yet a class of intractable problems to remain unsolved?
  - kingaillas 5y ago
    It would mean that a large class of problems that have solutions that can be verified quickly can be solved quickly. Which cuts both ways. While that means most protocols used for cryptography would need to be replaced (hashing, digital signatures, etc) it also means other combinatorics algorithms (traveling salesman, protein structure prediction) would become solvable which may been boon for logistics and/or computational science. (I think this is correct) If P=NP there will still be intractable problems; they would be ones where the solutions can't be verified in polynomial time... along the lines of verifying the solution is correct is as complicated as brute forcing the solution. Note: it's been a while since my computation theory class. ;) I am reading over https://en.wikipedia.org/wiki/P_versus_NP_problem https://en.wikipedia.org/wiki/P_versus_NP_problem and relearning the fine house of cards theoreticians have divided this problem into. There is a "consequences of P=NP" towards the bottom that sums it up better than I can.
    - xxpor 5y ago
      There's also the chance that while we may be able to come up with a polynomial algorithm for integer factorization, it's not actually practical to run still. Remember computational complexity discards the constants on that polynomial. Practically speaking x^2 + x is a lot different from 2^64x^2 + 2^32x + 2^16 :)
    - Dylan16807 5y ago
      'quickly' is doing a lot of work in that sentence. "A proof that P = NP could have stunning practical consequences if the proof leads to efficient methods for solving some of the important problems in NP." Note the "if". It is extremely important to the meaning. It's very possible for P to equal NP, but for that "if" to be false.
r00fus 5y ago
Yes. Just like in that movie Sneakers

snarf21 5y ago

Among other things, mostly encryption. Most of our current methods depends on P != NP. So no need for 0 days if you can just read at encrypted data as if it wasn't.

Dylan16807 5y ago
> Most of our current methods depends on P != NP. Not really. They depend on guessing being slow. P, just P, can do slow. P can be bigger than the universe even with low values of n.

kingaillas 5y ago

Well for one, the safety of encryption rests on certain problems being intractable. (In a theoretical sense; there are always implementation bugs that destroy security). If P=NP, then those previously thought to be intractable problems, are actually tractable. And the foundation of a lot of security-related engineering collapses.

nafey 5y ago
Is proving P = NP equivalent to knowing how any intractable problem can be solved? Is it possible for P=NP and yet a class of intractable problems to remain unsolved?
- kingaillas 5y ago
  It would mean that a large class of problems that have solutions that can be verified quickly can be solved quickly. Which cuts both ways. While that means most protocols used for cryptography would need to be replaced (hashing, digital signatures, etc) it also means other combinatorics algorithms (traveling salesman, protein structure prediction) would become solvable which may been boon for logistics and/or computational science. (I think this is correct) If P=NP there will still be intractable problems; they would be ones where the solutions can't be verified in polynomial time... along the lines of verifying the solution is correct is as complicated as brute forcing the solution. Note: it's been a while since my computation theory class. ;) I am reading over https://en.wikipedia.org/wiki/P_versus_NP_problem https://en.wikipedia.org/wiki/P_versus_NP_problem and relearning the fine house of cards theoreticians have divided this problem into. There is a "consequences of P=NP" towards the bottom that sums it up better than I can.
  - xxpor 5y ago
    There's also the chance that while we may be able to come up with a polynomial algorithm for integer factorization, it's not actually practical to run still. Remember computational complexity discards the constants on that polynomial. Practically speaking x^2 + x is a lot different from 2^64x^2 + 2^32x + 2^16 :)
  - Dylan16807 5y ago
    'quickly' is doing a lot of work in that sentence. "A proof that P = NP could have stunning practical consequences if the proof leads to efficient methods for solving some of the important problems in NP." Note the "if". It is extremely important to the meaning. It's very possible for P to equal NP, but for that "if" to be false.

r00fus 5y ago

Yes. Just like in that movie Sneakers