Boolean Functions and Computation Models

The foundations of computational complexity theory go back to Alan Thring in the 1930s who was concerned with the existence of automatic procedures deciding the validity of mathematical statements. In 1957, John von Neumann [vN58] wrote in his notes for the Silliman Lectures concerning the nature of computation and the human brain that .