3 ms·
The obvious proof term for isprime p is exponential compared to the size of p. The AKS proof term is polynomial, but still very bad.
by mathgradthrow 2y ago
The obvious proof term for isprime p is exponential compared to the size of p. The AKS proof term is polynomial, but still very bad.
- mathgradthrow 2y agohttps://en.m.wikipedia.org/wiki/Primality_certificate https://en.m.wikipedia.org/wiki/Primality_certificate