Allen Auditorium This talk will survey the history, meaning, and significance of the P vs. NP question. Could there be a miracle machine to efficiently perform all the problem solving work
of mathematics? To zip through problems of engineering design and discovery? The existence of such a miracle machine is exactly the question of P vs. NP. If P = NP, there would be a miracle machine that could take in any mathematical statement S and output
a proof of the statement in time polynomially bounded by the length of the shortest proof of S. In other words, our miracle machine could solve problems in time polynomially related to the length of the answer. Our faith in the "genius" of our own creativity leads us to conjecture that no such magic bullet problem solver exists. Is the conjecture that
P <> NP common sense or a result of failure of our imagination?
P vs. NP stands as one of the unsolved Clay Millennium Challenges to mathematics. In this talk, we will survey the role of P vs. NP in a much broader theory of computational complexity. We will touch on the major "approaches" and why they fall short.
Steven Rudich has been a Professor of Computer Science at Carnegie Mellon University since 1990. He received his Ph. D. in Computer Science from the University of California at Berkeley under the advisorship of Manuel Blum.
Professor Rudich's research expertise is in computational complexity theory, the mathe-matical foundations of cryptography, and in the often surprising interplay between the two areas. He has a special interest in the history, status, and resolution of the P vs. NP question.
Professor Rudich is the recipient of Carnegie Mellon's departmental and university-wide awards for teaching excellence, and was chosen by the Mathematical Association of America as Polya Lecturer(2004-2006). He is the director of Andrew's Leap, which is a summer program for gifted high school aged students to gain exposure to all aspects of computer science. Steven Rudich is also a gourmet cook and a professional close-up magician.