Science News of the Day #1: A P-time Primality Test
Three computer scientists at the Indian Institute of Technology in Kanpur have published a paper presenting a new algorithm for determining whether a given number is prime (evenly divisible only by itself and by one) or composite (evenly divisible by at least one number besides itself and one). The big deal is that they also present a proof that their algorithm runs in what computer scientists call polynomial time. It's been an open question in computation theory whether such an algorithm is possible, and if the paper is correct, then a big question has just been answered.
There's some great copy in the paper:
The ultimate goal of this line of research is, of course, to obtain an unconditional deterministic polynomial-time algorithm for primality testing. Despite the impressive progress made in primality testing so far, this goal has remained elusive. In this paper, we achieve this.I love that.
The New York Times has a good piece on this, and those inclined can read the paper itself (as a PDF).
Thanks, Mom!