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

Четверг, 22 сентября 2016, 18:30–19:50
ПОМИ РАН

Описание

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