Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Лекция 3. Машины Тьюринга. Элементы сложности доказательств.
Обзорный курс по теоретической информатике


Что: Лекция
Когда: Четверг, 22 сентября 2016, 18:30–19:50
Где: ПОМИ РАН

Описание

Машины Тьюринга. Моделирование машин Тьюринга схемами. NP-полнота задачи Circuit-SAT. Деревья поиска противоречия. Нижняя оценка на принцип Дирихле с помощью игр. Резолюционные доказательства и их связь с деревьями поиска противоречия.