Prize-winning piece of computer puzzle holds promise
Share with others:
Steven Rudich: CMU computer science professor shares 2007 Godel Prize.
Click photo for larger image.
Put on your intellectual seat belt. Steven Rudich will take your brain on a roller-coaster ride, then quiz you later on the details.
Hey, he is a renowned mathematician. He thrives on details.
Dr. Rudich, the 45-year-old professor of computer science at Carnegie Mellon University, will share the Association for Computing Machinery's 2007 Godel Prize for his work on what many consider the most important unresolved question in theoretical computer science.
He and Alexander A. Razborov, a mathematician and computational theorist at the Steklov Mathematical Institute in Moscow, will receive the $5,000 prize June 11-13 at the ACM Symposium on Theory of Computing in San Diego. It is one of the premier prizes in computer science and mathematics.
The two are being recognized for their collaborative work on the P vs. NP question, a classic puzzle that as Dr. Rudich's research proved, actually provides insights into the computational complexity that underlies the security of ATM cards, computer passwords and electronic commerce.
The two were able to reinterpret others' research so that it could be used to break a certain class of encrypted computer codes used in such devices as cell phones. Their unified theory resulting from their research has stood the test of time, prompting the prize.
The P vs. NP question is one of the seven millennium problems for which the Clay Mathematics Institute is offering $1 million to the solver. Dr. Rudich did not solve it. In fact, he said perhaps no one ever will.
But their work has helped explain the depth and difficulty of the question, while showing that baby steps others made in trying to solve the question actually were not valid. However, Drs. Rudich and Razborov's research showed that those works could be used for an unexpected purpose -- as a unified theory in breaking computer cryptography.
The P vs. NP question addresses the difference between one's ability to recognize creative accomplishment vs. one's ability to do the actual creative work. For example, Dr. Rudich used the analogy that he can recognize the genius of "Moby Dick," but recognizing its brilliance does not mean he can turn around and write a novel on par with Herman Melville's classic.
The key is producing a mathematical proof resolving the question one way or another.
Any formula, equation or process of algorithms that would allow computers to recognize a problem, or creative accomplishment, then generate comparable works or solutions, would represent the Holy Grail of computer science and solve the P vs. NP question.
Proof that P equals NP, or recognition could be transformed into creation, would be a magic bullet of creativity. But proving that P does not equal NP would provide a perfect method of cryptography. Either way, the proof or disproof would hold great value in computer science.
"The bottom line from my point of view is that this P vs. NP question is one of the greatest problems of the 20th and 21st centuries," said Richard Ladner, Boeing professor of computer science and engineering at the University of Washington. He served as chairman of one of the groups that awarded the prize.
Dr. Ladner compared it to a problem of finding the perfect route for a traveling salesman through 100 or 1,000 cities then returning to the original city without going through any city twice. If an optimal solution existed, it would be easy to recognize. Finding the perfect route is the problem.
Based in part on Dr. Rudich's research, however, most computer scientists and mathematicians are beginning to believe that recognizing a solution and using that recognition as a means of quick solution cannot be accomplished, Dr. Ladner said. Perhaps, P never can equal NP.
If so, Dr. Rudich's research would be a seminal work in disproving the P equals NP.
"I've met [Dr. Rudich] three or four times, and he's a fascinating individual," Dr. Ladner said. "He's very strong on education and built a lot of educational curriculum at CMU and in Pittsburgh.
"A lot of mathematicians do research in a vacuum, but I view him as a theoretician of the people."
Dr. Rudich, an accomplished magician, also is editor of the Journal of Cryptology and serves as director of Andrew's Leap, a highly selective summer program for Pittsburgh-area high school students interested in math and science. Two years ago, he was selected by the Mathematical Association of America as the Polya Lecturer for two academic years ending in 2006.
He said the P vs. NP question has been an obsession of his for decades, ever since he first read "Godel's Proof," when he was 12.
The 1994 papers by Drs. Rudich and Razborov brought efforts to solve the question to a screeching halt and helped convince many that it might be easier to disprove the question.
But their paper had an unexpected outcome. Drs. Rudich and Razborov showed that a wide class of proof techniques they call natural proofs cannot solve the P vs. NP question. But what they could do was provide a unified method for breaking a wide class of crypto-systems or computer codes.
Proving that P equals NP would rule the intellectual world. Any major problem could be solved quickly, Dr. Rudich said, be it cold fusion or any other scientific theory or even creation of great symphonies or novels. It could reduce creative genius to an immediate formula or algorithm process. The question remains one of the greatest challenges facing mathematicians.
"I'm a big believer in human creativity," Dr. Rudich said. "I am optimistic that someone -- maybe it won't be me -- will solve this."
First Published May 29, 2007 6:19 pm
