Boolean Functions and Computation Models

The book delves into the historical development of computational complexity theory, tracing its roots back to Alan Thring's inquiries in the 1930s about automatic procedures for validating mathematical statements. It explores key concepts such as the undecidability of the Halting Problem and the quantitative aspects of problem-solving, introducing contributions from notable figures like A. Cobham, M. Rabin, and C. Shannon. Additionally, it examines the philosophical implications of computation, particularly John von Neumann's reflections on the relationship between computation and human cognition.