2007 Gödel Prize

The 2007 Gödel Prize has been announced and the winners are Alexander Razborov and Steven Rudich for their “Natural Proofs” paper. Here is the citation:

The theory of Computer Science was developed to formalize methods for computation and the problems they can solve. The class P consists of the problems solvable by conventional computers in time polynomial in the input size. Another class of problems called NP requires one to find a solution of a problem where it is feasible to quickly verify that the solution is correct. Many NP problems have no known efficient solution even though they have major practical applications. The P =? NP question has challenged researchers in theoretical Computer Science for many decades and is at the core of the challenges facing this field. This question first began to be actively investigated in the early 1970s when Stephen Cook and Leonid Levin showed that the efficient solution of a “complete” problem for NP could be used to efficiently solve all of the problems in NP. To many in the field, this indicated that P is not likely to be equal to NP, but the question has been open for over 35 years since then. Researchers (Baker, Gill, and Solovay) in 1975 showed that certain general proof techniques known as diagonalization, which had been successfully used to provide proofs in theoretical computer science, could not be used to separate P and NP. In the two decades after that, researchers developed proofs that computational models known as circuits (similar to the circuits in conventional chips) could not solve certain computational problems, in the hope of generalizing those proofs to show that P is not NP. These proof methods, known as “circuit lower bounds,” generally restricted resources of circuits (such as size and/or depth) so the circuit could not solve a given problem. The Natural Proofs paper is concerned with showing that proof techniques using circuit lower bounds are not likely to resolve the P =? NP question. The paper formalizes some properties found in common in all known circuit lower bound proofs, and calls proofs having these properties “Natural Proofs”. The paper provides strong evidence that no Natural Proof separates P and NP, by showing that otherwise a widely held conjecture would be violated. This conjecture is that “pseudorandom number generators” exist; these are procedures that take at input a short random “seed” sequence of bits and then, without further use of randomness, generate a very long (exponential in the seed length) sequence of pseudo-random bits. The resulting pseudo- random bits are actually not random but appear, even to a very powerful computer running for a very long time, to be completely random. The existence of “pseudo-random number generators” is also related to the existence of unbreakable methods for cryptography, also widely conjectured to exist. The paper also proves, without any assumptions, that there is no Natural Proof that certain computational problems often used in cryptography (e.g., integer factoring and discrete log) are hard to solve. Such cryptographic methods are of critical use to electronic commerce, and though widely conjectured to be unbreakable, this implies that there are Natural Proofs for their security. In summary, the Natural Proofs paper proves that a wide class of proof techniques canu2019t be used to resolve the P =? NP and related questions, unless widely held conjectures are violated. The Natural Proofs paper impacts the efforts of generations of theoretical scientists that have worked to resolve the question of P =? NP, and implies that other proof techniques need to be applied (such as non-constructive methods which make use of techniques not allowed by Natural Proofs).