Hacker News Reader

Why do people keep repeating this notion? P doesn't mean fast or even tractable within the expected lifetime of the universe. "Polynomial time algorithms are fast" is an extremely vague statement for intuition, and not actually true except if you define carefully what you mean (that is, that they are faster as n->+inf...)

If crypto relies on some algorithms that are O(n^100000000000) where n is key length, I'm not very worried.

It wouldn't (probably) render the algorithms who rest upon the assumption that P!=NP useless. You still have to find a fast algorithm for the problem. Just because it is in P doesn't mean there exists a (practical) fast algorithm to break the crypto.

Vinay Deolalikar.