4 ms·
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 algorith
by andreasscherman 8y ago
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!
- allenz 8y agoYes, 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.