What are the limits of mathematical knowledge? The purpose of this chapter is to introduce the main concepts from computational complexity theory that are relevant to algorithmic accessibility of mathematical understanding. In particular, I'll discuss the P versus NP problem, its possible impact on research in mathematics, and how interested Gödel himself was in this computational viewpoint.

Much of the technical material will be necessarily sketchy. The interested reader is referred to the standard texts on computational complexity theory, primarily Arora and Barak (2009), Goldreich (2008), Papadimitriou (1994a), and Sipser (1997).

Overview

Hilbert believed that all mathematical truths are knowable, and he set the threshold for mathematical knowledge at the ability to devise a “mechanical procedure.” This dream was shattered by Gödel and Turing. Gödel's incompleteness theorem exhibited true statements that can never be proved. Turing formalized Hilbert's notion of computation and of finite algorithms (thereby initiating the computer revolution) and proved that some problems are undecidable – they have no such algorithms.

Though the first examples of such unknowables seemed somewhat unnatural, more and more natural examples of unprovable or undecidable problems were found in different areas of mathematics. The independence of the continuum hypothesis and the undecidability of Diophantine equations are famous early examples. This became known as the Gödel phenomenon, and its effect on the practice of mathematics has been debated since.