4 ms·
SAT problems, after all, are in the NP-complete class of problems, which means that they are damn hard to solve with current methods. ...and if they weren't, i
by userbinator 7y ago
SAT problems, after all, are in the NP-complete class of problems, which means that they are damn hard to solve with current methods.
...and if they weren't, it would have some very interesting implications for cryptography, one of which is that preimage attacks on hash functions would become much easier --- the SAT instance in this case is one that performs the computation of the function, equating each bit of desired output to equations of each of the input bits.
- bawolff 7y agoHonestly, that's probably the least interesting implication of a constructive proof that p=np. The entire field of cryptography is based around the idea of problems easy to solve with a short piece of information but hard to solve without it. If P=NP (and we have a constructive proof with an algorithm where the constants & degree aren't rediculous), the entire field of cryptography would collapse. Only 1-time pad's would be safe.
- GuB-42 7y agoPolynomial doesn't mean practical. In practice, O(n^100) is not an improvement over O(2^n). Also, we could imagine an algorithm that takes O(2^n) operation to verify and O(100^n) to find a solution. Both are exponential time (not NP), but the difference ensures that you can make it both safe and fast enough for use. I don't know if we could build such an algorithm if we had constructive P=NP though.
- bawolff 7y ago>Polynomial doesn't mean practical. In practice, O(n^100) is not an improvement over O(2^n). I literally said in my comment "and we have a constructive proof with an algorithm where the constants & degree aren't rediculous"