Gödel Prize for Natural Proofs

And speaking of awards... On the heels of congratulating the winners of the Intel Young Scientists, we should also recognize the contributions of Alexander Razborov and Steven Rudich who will be receiving the 2007 Gödel Prize for outstanding papers in theoretical computer science at the upcoming ACM Symposium on Theory of Computing.

The award is actually for a paper entitled Natural Proofs originally presented in 1994, where Razborov and Rudich explained that a wide class of proof techniques cannot be used to resolve P vs. NP Problem -- a classic question on the limits of proof and computation that has resisted resolution over the years. The problem applies to solving complex mathematical problems common in safeguarding ATM security, passwords, cryptography, authentication, access control, and e-commerce.

Their findings address a problem that is widely considered the most important question in computing theory. It has been designated as one of seven Prize Problems by the Clay Mathematics Institute, which has allocated $1 million for solving each problem. It asks -- if it is easy to check that a solution to a problem is correct, is it also easy to solve the problem? This problem is posed to determine whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve.

The paper proves that there is no so-called "Natural Proof" that certain computational problems often used in cryptography are hard to solve. Such cryptographic methods are critical to electronic commerce, and though these methods are widely thought to be unbreakable, the findings imply that there are no Natural Proofs for their security.

Razborov is a mathematician and computational theorist at the Russian Academy of Science Steklov Mathematical Institute. Rudich is Associate Professor of Computer Science at Carnegie Mellon University. The Gödel Prize, which includes an award of $5000, recognizes major contributions to mathematical logic and the foundations of computer science.

Posted by Jon Erickson at 09:06 AM  Permalink