Odpowiedzi:
Na początek jest oczywiście książka Arory i Baraka Computational Complexity: A Modern Approach . Stamtąd części 3 i 4 książki Jukny Boolean Function Complexity: Advances and Frontiers stanowią doskonały materiał do czytania. Ponadto Ryan Williams prowadzi fajny kurs na temat złożoności obwodów, którego notatki z kursu mogą być umieszczone online :)
Oprócz tych sugerowanych przez Arnaba poleciłbym również następującą książkę:
Wprowadzenie do złożoności obwodu: jednolite podejście autorstwa Heriberta Vollmera
Modele obliczeń autorstwa Johna E. Savage'a (więcej informacji / szczegółów / recenzji na amazon ). jest to w dużej mierze podręcznik dla studentów, ale wyróżnia się z punktu widzenia obwodu. zawiera wiele zaawansowanych tematów / dowodów i jest bezpłatny w Internecie i jest bardzo dobrze połączony za pomocą hiperłącza (spis treści, referencje, indeks itp.).