Steven Rudich

Steven Rudich is an American computer scientist and mathematician whose work in computational complexity theory has been foundational to our understanding of the limits of proof in circuit complexity. He is best known for his collaboration with Alexander Razborov on the natural proof barrier, a framework that demonstrates why a broad class of proof techniques cannot resolve the P versus NP problem.

The natural proof framework, introduced in 1994, revealed that any proof technique that is both constructive and sufficiently general would, if successful, break cryptographic pseudorandom generators. This result transformed the field of circuit complexity from a search for lower bounds into a study of the meta-mathematical constraints on what can be proven. Rudich's work extends the tradition of Kurt Gödel and Gregory Chaitin in showing that the complexity of the objects we study limits the complexity of the tools we can use to study them.