Computer scientist Steven Rudich of Carnegie Mellon and Alexander Razborov of Steklov Mathematical Institute in Moscow will share the Association for Computing Machinery’s 2007 Gödel Prize in June for their work on a problem regarding the sort of computational complexity behind the security of everything from ATM cards to computer passwords.
More specifically, the pair is being recognized with the $5,000 prize for their work on the P vs. NP question, which Carnegie Mellon explains like this:
” [It[ asks whether the class of problems with solutions that can be quickly recognized (complexity class NP) is the same as the class of problems with solutions that can be quickly generated (complexity class P). In human experience, it is intuitive that the ability to recognize something (like a good musical piece) is easy compared to being able to generate one yourself (like a good composer). People strongly suspect, based on a shared awe of creativity, that NP is a larger class than P. Cryptographers hope that is so; the security of all digital cryptographic systems requires it. At the same time, other computer scientists hope for the exact opposite – they hope to find unexpected shortcuts in the efficiency of creative problem-solving. To date, no one has formulated a mathematical proof that can answer the question one way or the other.”
The Gödel prize is named for Kurt Gödel, a 20th century mathematician and philosopher whose work helped lay the foundations for computer science.
“Of all of the prizes I could win, I would choose this one,” said Rudich, who is editor of the Journal of Cryptology . “Gödel has been my luminary hero since I was 12.”
I guess that’s what separates the Rudiches and Razborovs of the world from me. My luminary heroes at age 12 were a couple of rookie baseball players named Jim Rice and Fred Lynn who were leading the Red Sox to the World Series. Come to think of it, Jim Rice could probably use a good mathematician on his side to convince Hall of Fame voters that his numbers should earn him a spot in Cooperstown.
More on Carnegie Mellon’s network research efforts:
Microsoft joins forces with Carnegie Mellon University
Web site tracks ‘colorful’ mood swings
