Agrawal's conjecture [SEP] named after
Agrawal's conjecture
In number theory, Agrawal's conjecture, due to Manindra Agrawal in 2002, forms the basis for the cyclotomic AKS test. Agrawal's conjecture states formally:
Let formula_1 and formula_2 be two coprime positive integers. If 
then either formula_1 is prime or formula_5
Ramifications.
If Agrawal's conjecture were true, it would decrease the runtime complexity of the AKS primality test from formula_6 to formula_7.
Truth or falsehood.
The conjecture was formulated by Rajat Bhattacharjee and Prashant Pandey in their 2001
would run in Õ((log "n")) if Agrawal's conjecture is true; however, a heuristic argument by Hendrik Lenstra and Carl Pomerance suggests that it is probably false. A modified version of the Agrawal's conjecture, the Agrawal–Popovych conjecture, may still be true.
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