3 ms·
> What Manindra Agrawal, Neeraj Kayal and Nitin Saxena showed is that checking whether a given (binary) number is prime is in P. Wow this confused the hell out
by woojoo666 4y ago
> What Manindra Agrawal, Neeraj Kayal and Nitin Saxena showed is that checking whether a given (binary) number is prime is in P.
Wow this confused the hell out of me because I thought, isn't the sieve of eratosthenes already below polynomial time? But from what I read, while the sieve of eratosthenes is sub-polynomial relative to the magnitude of the input, the AKS method is polynomial time relative to the length of the input in binary representation (aka the number of binary digits).
- kadoban 4y agoYou're far from the first person to be confused by this, if it helps. https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time
- lupire 4y agoThat's funny because "most" NP-complete problems are pseudo-polynomial, because a simple exponential problem is O(e^polynomial), so log of that is polynomial. But people forget that natural numbers are just data, and that data can be interpreted at a a natural number.