5 ms·
https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test though it's number theory, and concerned with numbers of size
by qyph 2y ago
https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test though it's number theory, and concerned with numbers of size n, rather than lists of length n.
Also relevant: https://www.cs.yale.edu/homes/aspnes/pinewiki/Derandomization.html https://www.cs.yale.edu/homes/aspnes/pinewiki/Derandomizatio...
- dataflow 2y ago> https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test though it's number theory, and concerned with numbers of size n, rather than lists of length n. They were talking about not reading a lot of the input, so that's not it.
- Ar-Curunir 2y agoAKS is not sublinear. It runs in poly(n) time, where n is the number of bits in the input (i.e. input size).
- alok-g 2y agoFor that case, a better 'n' to use could be the number of digits in the number.