Primality test
Complexity

In computational complexity theory, the formal language corresponding to the prime numbers is denoted as PRIMES. It is easy to show that PRIMES is in Co-NP: its complement COMPOSITES is in NP because one can decide compositeness by nondeterministically guessing a factor.

In 1975, Vaughan Pratt showed that there existed a certificate for primality that was checkable in polynomial time, and thus that PRIMES was in NP, and therefore in N P ∩ c o N P {\displaystyle {\mathsf {NP\cap coNP}}}. See primality certificate for details.

The subsequent discovery of the Solovay–Strassen and Miller–Rabin algorithms put PRIMES in coRP. In 1992, the Adleman–Huang algorithm reduced the complexity to Z P P = R P ∩ c o R P {\displaystyle {\mathsf {{\color {Blue}ZPP}=RP\cap coRP}}}, which superseded Pratt's result.

The Adleman–Pomerance–Rumely primality test from 1983 put PRIMES in QP (quasi-polynomial time), which is not known to be comparable with the classes mentioned above.

Because of its tractability in practice, polynomial-time algorithms assuming the Riemann hypothesis, and other similar evidence, it was long suspected but not proven that primality could be solved in polynomial time. The existence of the AKS primality test finally settled this long-standing question and placed PRIMES in P. However, PRIMES is not known to be P-complete, and it is not known whether it lies in classes lying inside P such as NC or L. It is known that PRIMES is not in AC.
length_constraints:number_paragraphs[3]