Editing Primality test (section)

== 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 (complexity)|NP]], and therefore in {{tmath|\mathsf{NP \cap coNP} }}. See [[primality certificate]] for details.

The subsequent discovery of the Solovay–Strassen and Miller–Rabin algorithms put PRIMES in [[RP (complexity)|coRP]]. In 1992, the Adleman–Huang algorithm<ref name=AH92/> reduced the complexity to [[ZPP (complexity)|{{tmath|1=\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 (complexity)|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 (complexity)|NC]] or [[L (complexity)|L]]. It is known that PRIMES is not in [[AC0|AC<sup>0</sup>]].<ref>{{cite journal | url=https://doi.org/10.1006/jcss.2000.1725 | doi=10.1006/jcss.2000.1725 | title=A Lower Bound for Primality | date=2001 | last1=Allender | first1=Eric | last2=Saks | first2=Michael | last3=Shparlinski | first3=Igor | journal=Journal of Computer and System Sciences | volume=62 | issue=2 | pages=356–366 }}</ref>