You are here

Logical Foundations of Mathematics and Computational Complexity: A Gentle Introduction

Pavel Pudlák
Publication Date: 
Number of Pages: 
Springer Monographs in Mathematics
[Reviewed by
Tom Schulte
, on

This book lives up to its title. It spans the historical, logical, and at times philosophical underpinnings of the theory of computational complexity. Students of mathematics seeking a transition to higher mathematics will find it helpful, as will mathematicians with expertise in other areas. Philosophers and the philosophically inclined with a background in mathematics may be drawn to many chapters here. This is an excellent choice for a first text in studying complexity, or as a clarifying adjunct to any assigned text in this area.

There are two main parts of this book: introductory topics and then a deeper dive to complexity and its applications. The first three chapters introduce relevant basics: set theory, models, lambda calculus, statements of the First and Second Incompleteness Theorems, etc. In the final four chapters, the implications of incompleteness are explored. This includes impossibility proofs, algorithmically unsolvable problems, independence, consistency, and proof complexity. The chapters each has a summary of main points and each section has engaging Notes which enumerate further details on topics covered or give a quick paragraph on a related topic that could not be given full treatment.

The emphasis on essential explanation and abstracting ponderous proofs makes this a compact guide for graduate students with a need for or interest in computational complexity and its foundations. The author’s efficient and entertaining delivery manifestly derive from a mastery of and enthusiasm for this core area of mathematics.

Tom Schulte gently introduces students to mathematics at Oakland Community College.