Paterson M.S. (ed.) Boolean Function Complexity

Издательство Cambridge University Press, 1992, -211 pp.Complexity theory attempts to understand and measure the intrinsic difficulty of computational tasks. The study of Boolean Function Complexity reaches for the combinatorial origins of these difficulties. The field was pioneered in the 1950's by Shannon, Lupanov and others, and has developed now into one of the most vigorous and challenging areas of theoretical computer science.
In July 1990, the London Mathematical Society sponsored a Symposium which brought to Durham University many of the leading researchers in the subject for ten days of lectures and discussions. This played an important part in stimulating new research directions since many of the participants were meeting each other for the first time. This book contains a selection of the work which was presented at the Symposium. The topics range broadly over the field, representing some of the differing strands of Boolean Function Theory.
I thank the authors for their efforts in preparing these papers, each of which has been carefully refereed to journal standards. The referees provided invaluable assistance in achieving accuracy and clarity. Nearly all the referees' names appear also in the list of authors, the others being A. Wigderson, C. Sturtivant, A. Yao and W. McColl. While a measure of visual conformity has been achieved (all but one of the papers is set using LATEX), no attempt was made to achieve uniform notation or a 'house style'. I have tried to arrange the papers so that those which provide more introductory material may serve to prepare the reader for some more austere papers which follow. Some background in Boolean complexity is assumed for most of the papers. A general introduction is offered by the three books by Dunne, Savage and Wegener which are referenced in the first paper.
The Symposium at Durham was made possible by the initiative and sponsorship of the London Mathematical Society, the industry and smooth organization of the staff at Durham University, the financial support of the Science and Engineering Research Council and by the enthusiastic participation of the Symposium members. Finally, I thank the staff and Syndics of Cambridge University Press for their cooperation and patience during the preparation of this volume.
Relationships Between Monotone and Non-Monotone Network Complexity.On Read-Once Boolean Functions
Boolean Function Complexity: a Lattice-Theoretic Perspective
Monotone Complexity
On Submodular Complexity Measures
Why is Boolean Complexity Theory so Difficult?
The Multiplicative Complexity of Boolean Quadratic Forms, a Survey
Some Problems Involving Razborov-Smolensky Polynomials
Symmetry Functions in AC0 can be Computed in Constant Depth with Very Small Size
Boolean Complexity and Probabilistic Constructions
Networks Computing Boolean Functions for Multiple Input Values
Optimal Carry Save Networks