Abstract

Monotone networks have been the most widely studied class of restricted Boolean networks. It is now possible to prove superlinear (in fact exponential) lower bounds on the size of optimal monotone networks computing some naturally arising functions. There remains, however, the problem of obtaining similar results on the size of combinational (i.e. unrestricted) Boolean networks. One approach to solving this problem would be to look for circumstances in which large lower bounds on the complexity of monotone networks would provide corresponding bounds on the size of combinational networks.

In this paper we briefly review the current state of results on Boolean function complexity and examine the progress that has been made in relating monotone and combinational network complexity.

Introduction

One of the major problems in computational complexity theory is to develop techniques by which non-trivial lower bounds, on the amount of time needed to solve ‘explicitly defined’ decision problems, could be proved. By ‘nontrivial’ we mean bounds which are superlinear in the length of the input; and, since we may concentrate on functions with a binary input alphabet, the term ‘explicitly defined’ may be taken to mean functions for which the values on all inputs of length n can be enumerated in time 2cn for some constant c.

Classical computational complexity theory measures ‘time’ as the number of moves made by a (multi-tape) deterministic Turing machine. Thus a decision problem, f, has time complexity, T(n) if there is a Turing machine program that computes f and makes at most T(n) moves on any input of length n.