Вы здесь

Основы вычислимости и теории сложности. Лекция 11

Лекция
Партнёр:
Предмет:
Дата записи:
28.11.12
Дата публикации:
28.11.12
Код для блога:

Нижние оценки для SAT. Схемная сложность

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

Страница лекции на сайте Computer Science Center

Другие лекции курса

11