Сложность булевых функций

Реализация булевых функций формулами, схемами, автоматами и машинами Тьюринга. Сложность функции.
Сложность систем линейных булевых функций.
Оценки сложности и глубины вычисления префиксных сумм.
Оценки сложности и глубины арифметических операций над целыми числами.
Оценки сложности быстрого преобразования Фурье и умножения многочленов. Асимптотические методы реализации булевых функций схемами и формулами.
Оценки сложности вычисления монотонных булевых функций.
Вычисления с ограниченной памятью.
Схемы на плоскости и их сложность (площадь).
Схемы в 3-х мерном пространстве и их сложность (объем).
Самокорректирующиеся схемы.
Моделирование схем автоматами и машинами Тьюринга.
Теорема Кука. NP-полные задачи.