4 ms·

Could the AKS primality test, which showed that PRIMES is in P, be implemented as an honest regular expression? Presumably not because then we'd know that PRIM

by evanb 3y ago

Could the AKS primality test, which showed that PRIMES is in P, be implemented as an honest regular expression? Presumably not because then we'd know that PRIMES is not just in P but is a regular language, which would be too good to be true. https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test

aleph_minus_one 3y ago
Via the pumping lemma, you can easily prove that testing whether a number is a prime number cannot be implemented as a regular expression.
- Tainnor 3y ago
  Via the context-free pumping lemma, you can even prove that prime numbers don't form a context-free language either.
  - taejo 3y ago
    And via Parikh's theorem, with a one-symbol alphabet, regular and context-free languages are the same.