CMU professor honored for computational complexity breakthrough

May 21, 2007

Computer scientists at Carnegie Mellon University and the Russian Academy of Science will share the Association for Computing Machinery's 2007 Gödel Prize for their seminal work on what many consider the most important unresolved question in theoretical computer science.

Steven Rudich, professor of computer science at Carnegie Mellon, and Alexander A. Razborov, a mathematician and computational theorist at the Steklov Mathematical Institute in Moscow, will receive the $5,000 prize at the ACM Symposium on Theory of Computing, June 11–13 in San Diego.

The ACM's Special Interest Group on Algorithms and Computing Theory recognized Rudich and Razborov for their work on the P vs. NP problem, a classic question concerning computational complexity that underlies the security of ATM cards, computer passwords and electronic commerce. It is literally a million-dollar question — one of seven Millennium Problems that the Clay Mathematics Institute has offered $1 million for solving.

The Gödel prize is named for Kurt Gödel (1906–1978), an Austrian-American mathematician and philosopher who had a major impact on the foundations of computer science and was among the first to puzzle over the P vs. NP problem.

"Of all of the prizes I could win, I would choose this one," Rudich said. "Gödel has been my luminary hero since I was 12."

The P vs. NP question 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.

Findings by Rudich and Razborov brought decades of work to find such a proof to a screeching halt. In a paper presented at the Symposium on Theory of Computing in 1994 and published in 1997 in the Journal of Computer and System Sciences, they showed that a wide class of proof techniques they call "natural proofs" can't solve the P vs. NP question. What's more, they found that those previous results turned out to have an almost contradictory double life, providing methods for breaking a wide class of cryptosystems.

That's not to say that a mathematical proof for P vs. NP is impossible, Rudich said, but it will have to be very different from the natural proofs that mathematicians had been employing.

To date, no one has convincingly devised such a proof, but Rudich is among those who are trying. "I've devoted my life to this question," he said. And if he can't solve it, he's convinced someone will. "I'm a big believer in human creativity."

Rudich is editor of the Journal of Cryptology and was selected by the Mathematical Association of America as Pólya Lecturer for the 2004–2005 and 2005–2006 academic years. An accomplished magician, he also serves as director of Andrew's Leap, a highly selective summer program for Pittsburgh-area high school students interested in math and science.

Razborov is an editor of the Theoretical Computer Science journal and was awarded the Nevanlinna Prize of the International Mathematical Union in 1990 for his contributions to complexity theory.

Source: Carnegie Mellon University

Explore further: Big data paves the way for big building and engineering projects

Related Stories

Fitness app connects exercisers to experts

Mar 24, 2015

Can advanced networking and next-generation applications help solve some of our nation's most pressing health problems? Can mobile devices and high-speed Internet be used to improve our health and well-being? ...

Facebook artificial intelligence team serves up 20 tasks

Mar 05, 2015

In August last year, Daniela Hernandez wrote in Wired about Yann LeCun, director of AI Research at Facebook. His interests include machine learning, audio, video, image, and text understanding, optimization, computer architecture and software for AI. ...

Are you afraid of technology? You shouldn't be

Mar 18, 2015

Nary a week goes by that doesn't see a new mainstream media story on the dangers of technology use. Just the other day I spotted one talking about how smartphones are making us dumber. ...

IBM's 'Jeopardy!' champ ventures to new worlds

Mar 13, 2015

IBM Watson initially won fame as the artificially intelligent computer system that won $1 million for whipping former "Jeopardy!" champs Ken Jennings and Brad Rutter on the televised game show in 2011.

Recommended for you

Colombia transforms old tires into green housing

10 hours ago

The highlands around the Colombian capital are scattered with small buildings that look like out-of-place igloos but are in fact innovative houses made from the tires that litter the country's roads.

LifePaint spray is Volvo's safety offer for cyclists

10 hours ago

For cyclists sharing the road at dark with cars and pedestrians, a useful motto is to stay safe by staying seen. Volvo, which continues to build on its brand of safety-first, has come out with LifePaint. ...

User comments : 0

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.