4 ms·
Precisely. In the case of the NP-hard example I presented below, the researcher (who's name eludes me) attempted to prove that a solution did not exist. From a
by ckozlowski 13y ago
Precisely. In the case of the NP-hard example I presented below, the researcher (who's name eludes me) attempted to prove that a solution did not exist.
From a computer science perspective, this would be favorable, as a solution for NP-hard would render a lot of crypto useless overnight. =P
- Genmutant 13y agoIt 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.
- psuter 13y agoVinay Deolalikar.
- umanwizard 13y agoWhy 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.