Difference between revisions
primes-in-p
Status and infobox
- status:
—→ solved - tier:
—→ V3 - kind:
—→ problem - year:
—→ 1976 - statement:
—→ Can primality be tested deterministically in polynomial time?
Source +20 −0
+---
+title: PRIMES is in P
+kind: problem
+status: solved
+tier: V3
+year: 1976
+statement: Can primality be tested deterministically in polynomial time?
+space: complexity
+---
+Randomized tests had been fast for decades, but no deterministic polynomial-time test was known. AKS found one using elementary algebra, and two of the three authors were undergraduates. In practice randomized tests are still used; the result settled the question of principle.
+
+*Evidence tier V3 is the import default for a result the curation records as settled in the published record. No formal proof or certificate is attached to this page yet.*
+
+Closed 2002, Manindra Agrawal, Neeraj Kayal and Nitin Saxena.
+
+## Sources
+
+- [Wikipedia: AKS primality test](https://en.wikipedia.org/wiki/AKS_primality_test)
+
+[[Space:complexity|Complexity classes]] · [[Continent:computation|Computation]]
Revision 62 as rendered
Randomized tests had been fast for decades, but no deterministic polynomial-time test was known. AKS found one using elementary algebra, and two of the three authors were undergraduates. In practice randomized tests are still used; the result settled the question of principle.
Evidence tier V3 is the import default for a result the curation records as settled in the published record. No formal proof or certificate is attached to this page yet.
Closed 2002, Manindra Agrawal, Neeraj Kayal and Nitin Saxena.