Proofs as efficient programs

What is a proof for? What is the characteristic use of a proof as a computation, as opposed to its use as an experiment? What is the relationship between mathematical procedures and natural processes? The essays collected in this volume address such questions from different points of view and will interest students and scholars in several branches of scientific knowledge. Some essays deal with the logical skeleton of deduction, others examine the interplay between natural systems and models of computation, yet others use significant results from the natural sciences to illustrate the character of procedures in applied mathematics. Focusing on relevant conceptual and logical issues underlying the overall quest for proving, the volume seeks to cast light on what the effectiveness of proof rests on. In the specific paper, we discuss the use of the Curry-Howard correspondence in computational complexity theory, the area of theoretical computer science concerned with the definition and study of complexity classes and their relations.