scientific article; zbMATH DE number 139642
[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.
- Models of lower-bounds proofs
- Easy lower bound for a strange computational model
- Lower bounds for unrestricted Boolean circuits: open problems
- Applications of matrix methods to the theory of lower bounds in computational complexity
- On a hierarchy of Boolean functions hard to compute in constant depth
- scientific article; zbMATH DE number 981681 (Why is no real title available?)
- Diagonalization strikes back: some recent lower bounds in complexity theory
- scientific article; zbMATH DE number 4172392 (Why is no real title available?)
- Complexity Lower Bounds using Linear Algebra
- Linear FPT reductions and computational lower bounds
- scientific article; zbMATH DE number 3916179 (Why is no real title available?)
- scientific article; zbMATH DE number 3934407 (Why is no real title available?)
- A Gödel Theorem on Network Complexity Lower Bounds
- scientific article; zbMATH DE number 4059378 (Why is no real title available?)
- scientific article; zbMATH DE number 4087011 (Why is no real title available?)
- Combinatorial properties of classes of functions hard to compute in constant depth
- scientific article; zbMATH DE number 1498462 (Why is no real title available?)
- Unexpected upper bounds on the complexity of some communication games
- scientific article; zbMATH DE number 3992933 (Why is no real title available?)
- A nonlinear lower bound on the practical combinational complexity
- A nonlinear lower bound on the practical combinational complexity
- A uniform method for proving lower bounds on the computational complexity of logical theories
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4029623)
