Re:A Short Guide to Hard Problems
by ouid on Tuesday July 17, 2018 @12:54PM
(#17551132)
It’s worth mentioning that the discovery of a deterministic polynomial time algorithm to determine primality is pretty recent, 2002. https://en.m.wikipedia.org/wiki/AKS_primality_test
[ Parent
| on HN ]
It's also worth mentioning that AKS didn't have much impact on practical cryptography. The probabilistic algorithms for checking primality are (and were) much faster, and have a tolerably-low chance of failure in selecting prime numbers for crypto.
I bring this up because, one (heuristic) reason to believe BPP=P is that, in practice, moving PRIMES from BPP to P didn't make a difference.
someone (recently?) constructed a composite number which failed miller rabin for 400 iterations or something.
Re:A Short Guide to Hard Problems
by andreasscherman on Wednesday July 18, 2018 @02:59AM
(#17556017)
To help anyone who was as confused as I about this being the first polynomial time algorithm. To me, even the naïve primality test is a polynomial time algorithm over the target number. However, here the AKS primality test is a polynomial time algorithm over the number of digits in the target number, which of course is different!
Yes, time complexity is based on the length of the input to a Turing machine. For example, integer factorization is a hard problem because all known algorithms are roughly exponential in the number of bits.