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

Лекция 2. Короткие доказательства и класс NP
Обзорный курс по теоретической информатике


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

Описание

Определение класса NP, примеры. Доказательство простоты числа (критерий Пратта). Сведения и полнота. NP-полнота задачи об ограниченной остановке. Сведение Circuit-SAT к 3SAT.