City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Нижние оценки для SAT. Схемная сложность
Foundations of computability and complexity theory

What: Lecture
When: Wednesday, 28 November 2012, 18:30–19:50
Where: ПОМИ РАН

Description

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

Video