Город: Язык: Русский English
Что: Лекция
Когда: Среда, 08 октября 2014, 18:30–19:50
Где: ПОМИ РАН

Описание

Системы доказательств и перечислимые языки. Нижняя оценка на палиндром на одноленточной машине. Моделирование машин Тьюринга. Недетерминированные машины Тьюринга. Определения класса NP. Примеры. Сведения по Карпу. Понятние полноты. Полнота задачи об ограниченной остановке. Полнота задачи SAT и 3-SAT.