Superpolynomial lower bounds on monotone network complexity
Paul E.S. Dunne · Cambridge University Press eBooks · 1990
Combinational networks are a widely studied model for investigating the computational complexity of Boolean functions relevant both to sequential computation and parallel models such as VLSI circuits. Recently a number of important results proving non-trivial lower bounds on a particular type of restricted network have appeared. After giving a general introduction to Boolean complexity theory and its history this chapter presents a detailed technical account of the two main techniques developed for proving such bounds. INTRODUCTION An important aim of Complexity Theory is to develop techniques for establishing non-trivial lower bounds on the quantity of particular resources required to solve specific problems. Natural resources, or complexity measures , of interest are Time and Space, these being formally modelled by the number of moves made (resp. number of tape cells scanned) by a Turing machine. ‘Problems’ are viewed as functions, f : D → R; D is the domain of inputs and R the range of output values. D and R are represented as words over a finite alphabet Σ and since any such alphabet can be encoded as a set of binary strings it is sufficiently general to consider D to be the set of Boolean valued n -tuples {0, 1} n and R to be {0,1}. Functions of the form f : {0, 1} n → {0,1}, are called n -input single output Boolean functions. B n denotes the set of all such functions and X n = ( x 1 , x 2 , …, x n ) is a variable over {0, 1} n .