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