Boolean Function Complexity

ISBN: 9780521408264 出版年：1992 页码：214 M S Paterson Cambridge University Press

1. Relationships between monotone and non-monotone network complexity 2. On read-once Boolean functions 3. Boolean function complexity: a lattice-theoretic perspective 4. Monotone complexity 5. On submodular complexity measures 6. Why is Boolean complexity so difficult? 7. The multiplicative complexity of Boolean quadratic forms 8. Some problems involving Razborov-Smolensky polynomials 9. Symmetry functions in AC0 10. Boolean complexity and probabilistic constructions 11. Networks computing Boolean functions for multiple input values 12. Optimal carry save networks.