Boolean Function Complexity
Seiten
1992
Cambridge University Press (Verlag)
978-0-521-40826-4 (ISBN)
Cambridge University Press (Verlag)
978-0-521-40826-4 (ISBN)
Boolean function complexity has seen exciting advances in the last few years. It is a long established area of discrete mathematics which uses combinatorial and occasionally algebraic methods.
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.
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.
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.
| Erscheint lt. Verlag | 5.11.1992 |
|---|---|
| Reihe/Serie | London Mathematical Society Lecture Note Series |
| Zusatzinfo | Worked examples or Exercises |
| Verlagsort | Cambridge |
| Sprache | englisch |
| Maße | 151 x 227 mm |
| Gewicht | 315 g |
| Themenwelt | Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre |
| ISBN-10 | 0-521-40826-1 / 0521408261 |
| ISBN-13 | 978-0-521-40826-4 / 9780521408264 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
Mehr entdecken
aus dem Bereich
aus dem Bereich
Buch | Softcover (2024)
World Scientific Publishing Co Pte Ltd (Verlag)
CHF 43,60
what we have that machines don't
Buch | Softcover (2024)
Profile Books Ltd (Verlag)
CHF 19,15
how simple questions lead us to mathematics’ deepest truths
Buch | Softcover (2024)
Profile Books Ltd (Verlag)
CHF 19,15
