Wegener I. The Complexity of Boolean Functions

Издательство John Wiley, 1987, -469 pp.Различные аспекты теории сложности: булевы функции, схемы, формулы, программы итд.
Булевы функции и схемы.
Минимизация булевых функций.
Разработка эффективных схем для некоторых важных функций.
Асимптотики и универсальные схемы.
Нижние границы сложности схем.
Монотонные схемы.
Связь между сложностью схем, сложностью формул и их глубиной.
Сложность формул.
Схемы vs. машин Тьюринга.
Иерархии, массовые произведения и редукции.
Схемы ограниченной глубины.
Синхронные, планарные и вероятностные схемы.
PRAM’ы и WRAM’ы.
Ветвящиеся программы.