| Description |
1 online resource (201 pages) : illustrations |
| Series |
London Mathematical Society lecture note series ; 169 |
|
London Mathematical Society lecture note series ; 169.
|
| Contents |
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 |
|
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 |
| Summary |
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 |
| Notes |
Papers from the Symposium on Boolean Function Complexity, held July, 1990, at Durham University and sponsored by the London Mathematical Society |
| Bibliography |
Includes bibliographical references (pages 198-201) |
| Notes |
Print version record |
| Subject |
Computational complexity -- Congresses
|
|
Algebra, Boolean.
|
|
MATHEMATICS -- Algebra -- General.
|
|
Algebra, Boolean
|
|
Computational complexity
|
|
Komplexitätstheorie
|
|
Boolesche Funktion
|
|
Boolean-functions.
|
|
Boole, algèbre de -- Congrès.
|
|
Complexité de calcul (Informatique) -- Congrès.
|
| Genre/Form |
Conference papers and proceedings
|
| Form |
Electronic book
|
| Author |
Paterson, Michael S
|
| LC no. |
93111192 |
| ISBN |
9781107361720 |
|
1107361729 |
|
9780511526633 |
|
0511526636 |
|
