Mathematics, Proofs and Computation

Madhu Sudan (Harvard University)

While it is well-understood that Proofs form the foundations of Mathematics, it is less well-known that Proofs and Computers are intimately related. Indeed a common perception is that the only link between Proofs and Computing is that sometimes computers can assist in the search for proofs.  In this talk I will describe a more historically significant, and intrinsic, connection. Proofs are by definition "Computational Objects" - and to understand to the difference between a theorem and its proof, one needs to understand computational complexity of tasks - namely the number of steps on a computer needed to solve a given task. In this talk, I will talk about the historical role of proofs in computation, leading to the "prototype" of the modern computer in the 1930s, to the conception of the famous "Is P = NP?" question in the 1970s and some modern variation like interactive proofs, zero-knowledge proofs and probabilistically checkable proofs. I will explain how at each stage the study of proofs has revolutionized our understanding of what computers can or can  not do!