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. The first example of such a problem was the undec...