« Aortal: language hat | Main | Science News of the Day #2: Speed of Light Decreasing? »

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!

Post a comment

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)