Primality is a problem hanging onto a cliff above P with its grip continuing to loosen each day. - Paraphrased from a talk given by Juris Hartmanis in 1986.
It took sixteen more years but the primality problem did fall.
This paper gave the first provably deterministic polynomial-time algorithm that could determine whether n is a prime given n in binary. The theoretical importance cannot be overstated. But why do I consider the paper a complexity result instead of just an algorithmic result?
Manindra Agrawal had already a strong reputation as a complexity theorist. The proof involves a derandomization technique for a probabilistic algorithm for primality. But more importantly primality had a long history in complexity.
Primality is in co-NP almost by definition. In 1975, Vaughn Pratt showed that PRIMES is in NP. In 1977, Solovay and Strassen showed that PRIMES in co-RP and testing primality became the standard example of a probabilistic algorithm. In 1987, Adleman and Huang building on work of Goldwasser and Kilian showed that PRIMES is in RP and thus in ZPP. In 1992, Fellows and Koblitz showed that PRIMES is in UP∩co-UP. Finally in 2002 came AKS putting PRIMES in P.
A runner-up in this area is the division problem recently shown to be in logarithmic space and below.
