No label defined (Q4029623)

[For the entire collection see Zbl 0745.00057.] One of the hardest tasks in complexity theory is to prove nontrivial lower bounds on the amount of computational resources needed to compute concrete computing problems. This paper is devoted to lower bound proof techniques for combinational complexity (the number of gates of Boolean circuits). To prove a nonlinear lower bound on the combinational complexity of a specific Boolean Function is one of the most challenging problems of complexity theory. It remains more than 40 years open, despite of the well-known fact that almost all (random) Boolean functions have exponential combinational complexity. The author of this paper presents an overview of lower bound methods used to get linear lower bounds on combinational complexity, and searches for reasons explaining the hardness of proving a nonlinear lower bound.