Вычисления с ограничением по времени и по памяти. Нижняя оценка для SAT. Альтернирующие машины Тьюринга и полиномиальная иерархия. Булевы схемы. Вычисления с подсказкой. Класс P/poly. Включение P в P/poly. Теорема Карпа-Липтона. Существование функций большой схемной сложности.