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!
[ Parent
| on HN ]
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.