Guter Text zur Einführung in die Schaltungskomplexität

Ich möchte um Vorschläge für gute Texte bitten, die die Schaltungskomplexität einführen. Hinweise auf jüngste Fortschritte und offene Probleme in diesem Bereich wären ebenfalls hilfreich.

Zu Beginn gibt es natürlich Aroras und Baraks Buch Computational Complexity: A Modern Approach . Von dort aus sind die Teile 3 und 4 von Juknas Buch Boolean Function Complexity: Advances and Frontiers ein hervorragendes Lesematerial. Außerdem unterrichtet Ryan Williams einen schönen Kurs über die Komplexität von Schaltkreisen, dessen Kursnotizen hoffentlich online gestellt werden können :)

Zusätzlich zu den von Arnab vorgeschlagenen würde ich auch das folgende Buch empfehlen:

Einführung in die Schaltungskomplexität: Ein einheitlicher Ansatz von Heribert Vollmer

Modelle der Berechnung durch John E Savage (mehr Info / Detail / Berichte auf Amazonas ). Es ist größtenteils ein Lehrbuch für Studenten, zeichnet sich jedoch durch seine schaltungsorientierte Sichtweise aus. Enthält viele fortgeschrittene Themen / Beweise und ist kostenlos online und sehr gut verlinkt (Inhaltsverzeichnis, Verweise, Index usw.).