Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Favorite Theorems: Primality

Expand Messages
  • Lance Fortnow
    March Edition 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
    Message 1 of 2 , Apr 13, 2004
    • 0 Attachment
      March Edition

      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.

      PRIMES is in P by Manindra Agrawal, Nitin Saxena and Neeraj Kayal.

      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.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 4/13/2004 10:28:12 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.