3 ms·
> verifying solutions is much easier than finding them If P = NP Bitcoin breaks down. Interesting.
by rchowe 16y ago
> verifying solutions is much easier than finding them
If P = NP Bitcoin breaks down. Interesting.
- knowtheory 16y agoI mean... the whole secure internet breaks down if P = NP. The world will be a new and different place if we find out that P = NP.
- tzs 16y agoWell, maybe it breaks down, maybe not. If P = NP, that doesn't mean there are practical algorithms in P for the problems in NP. It could turn out that for all the problems in NP that we currently think aren't in P, the solutions in P are O(n^100000). Also, it can go the other way. Just because a problem is NP complete doesn't mean that if P != NP we can't solve it efficiently in practice. It just means we can't get an efficient algorithm that will work in every single case. It may turn out that the problem instances that actually come up in real life are amenable to fast solutions.