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

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

Что: Лекция
Когда: Понедельник, 21 сентября 2020, 18:30–19:50
Где: Конференция в zoom, Онлайн

Описание

Эффективные системы доказательств. Класс NP. Критерий Пратта и доказательство простоты числа. Класс P. Сведения, полные задачи. NP-полнота задачи об ограниченной остановке. Булевы схемы. Сведение Circuit-SAT к 3SAT.

Видео

Другие материалы

Текущая версия конспекта.