UID:
almafu_9959239106502883
Format:
1 online resource (201 pages) :
,
digital, PDF file(s).
ISBN:
1-139-88636-3
,
1-107-36663-1
,
1-107-37132-5
,
1-107-36172-9
,
1-107-36845-6
,
1-299-40439-1
,
1-107-36417-5
,
0-511-52663-6
Series Statement:
London Mathematical Society lecture note series ;
Content:
By considering the size of the logical network needed to perform a given computational task, the intrinsic difficulty of that task can be examined. Boolean function complexity, the combinatorial study of such networks, is a subject that started back in the 1950s and has today become one of the most challenging and vigorous areas of theoretical computer science. The papers in this book stem from the London Mathematical Society Symposium on Boolean Function Complexity held at Durham University in July 1990. The range of topics covered will be of interest to the newcomer to the field as well as the expert, and overall the papers are representative of the research presented at the Symposium. Anyone with an interest in Boolean Function complexity will find that this book is a necessary purchase.
Note:
Title from publisher's bibliographic system (viewed on 05 Oct 2015).
,
Cover; Title; Copyright; Contents; Preface; List of Participants; Relationships Between Monotone and Non-Monotone Network Complexity; Abstract; 1. Introduction; 2. Monotone boolean networks; 3. A framework for relating combinational and monotone network complexity; 4. Slice functions and their properties; 5. Conclusion; 6. Further reading; 7. Appendix - another application of theorem 3.5; References; On Read-Once Boolean Functions; Abstract; 1. Introduction; 2. Definitions and notations; 3. Characterization of read-once functions and generalizations; 3.1. Characterization
,
3.2. Generalization to read-once on a subset of the variables3.3. Functions with the t-intersection property.; 4. Read-once functions and the randomized boolean decision tree model; Acknowledgments; References; Boolean Function Complexity: a Lattice-Theoretic Perspective; Abstract; 1. Introduction; 2. Boolean computation: a lattice-theoretic view; 2.1. Computational equivalence and replaceability; 2.2. The case of distributive lattices; 2.3. Applications; 3. An alternative model for free distributive lattices; 3.1. Characteristics of the combinatorial model
,
3.1.1. Combinatorially piecewise-linear maps3.1.2. Dual cpl maps; 3.1.3. Chains and cycles of singular edges; 3.2. Cycles of singular edges as relations in Σn; 4. Conclusions and directions for further work; 5. Acknowledgments; References; Monotone Complexity; 1. Introduction; 2. Monotone complexity; 2.1. Monotone functions; 2.2. Monotone computational models; 2.3. Monotone complexity classes; 2.4. Monotone simulations; 2.5. Trivial monotone classes; 2.6. Rephrasing known results; 2.7. Monotone Separations; 3. Separating mNL from co-mNL; 3.1. Semi-unbounded circuits; 3.2. The separation
,
4. Towards Separating mBWBP from mNCL4.1. A lower bound on size; 4.2. There is no monotone barrington gadget; 5. Conclusion; References; On Submodular Complexity Measures; 1. Introduction; 2. Definitions and example of submodular complexity measures; 3. Main result; References; Why is Boolean Complexity Theory so Difficult?; 1. Introduction; 2. Algebraic structures; 3. Cancellations in the samuelson-berkowitz algorithm; 4. Simultaneous lower bounds on size and depth; References; The Multiplicative Complexity of Boolean Quadratic Forms, a Survey.; 1. Introduction
,
2. The multiplicative complexity of single boolean quadratic forms3. Independence and lower bounds for two boolean quadratic forms; 4. The multiplicative complexity of pairs of quadratic boolean forms; References; Some Problems Involving Razborov-Smolensky Polynomials; 1. Introduction; 1.1. Polynomials and circuit complexity; 1.2. The programs-over-monoid model; 1.3. Polynomials and programs over groups; 2. The small image-set conjecture; 3. The intersection conjecture; 4. Making change in an abelian group; 5. Consequences; 6. Acknowledgements; References
,
Symmetry Functions in AC0 can be Computed in Constant Depth with Very Small Size
,
English
Additional Edition:
ISBN 0-521-40826-1
Language:
English
