There are hard problems where the worst case may be exponentially hard, but the average case is much faster. Linear programming and the traveling salesman problem are like that. The faster approaches are considered "probabilistic solutions".

In cryptography, most of the problems believed to be exponentially hard, such as factoring, don't have proofs of an exponential lower bound. There's some risk of a breakthrough that makes those problems easier. A probabilistic solution would be good enough to break many cryptosystems.

I suspect that people at the cryptanalysis agencies worldwide are staying up late tonight, trying to figure out the impacts and risks of this new result.