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

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