4 ms·
> It's almost as bad as if someone proved P = NP, rendering all cryptography useless on the spot. No, P=NP does not immediately break crypto, because that rela
by blattimwind 9y ago
> It's almost as bad as if someone proved P = NP, rendering all cryptography useless on the spot.
No, P=NP does not immediately break crypto, because that relation makes no statement w.r.t. if those algorithms in P solving problems we thought were NP are easy to find. Or efficient. Just because the problem your adversary has to break is part of P doesn't make it easy.
- murbard2 9y agoTechnically, if P=NP then we already have a working algorithm to solve NP problems in polynomial time. It involves iterating through and running all possible programs ordered by length, giving them an increasing amount of time to run and checking (in polynomial time) if they produce the correct answer. If there exists a program that finds the answer in polynomial time, this algorithm will eventually find it after wasting (at most polynomial) time iterating through other programs and tentative bounds. If P != NP, it's still at least asymptotically optimal.
- sdenton4 9y agoHmm, but running 'all possible programs' is an exponential time operation (in the lengths of the programs)...
- murbard2 9y agoYes, but as you note, "in the size of the program" and the size of {the program that solves 3-SAT in polynomial time if there is one} is a constant, so it's all constant. Of course, that constant is astronomically unpractical.
- ufo 9y agoI like the term "Galactic Algorithm" for these algorithms with unpractical constants. https://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/ https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...
- Tloewald 9y agoPolynomial time is unbounded. Indeed constant Time is unbounded.