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

Лекция 2. Класс NP, недетерминированные машины Тьюринга.
Теория сложности вычислений

Что: Лекция
Когда: Вторник, 21 сентября 2021, 18:30–19:50
Где: Конференция в zoom, Онлайн
Слайды: computationalcomplexity_lecture_210921.pdf

Описание

Включение P в P/poly. Эффективная система доказательств. Класс NP, примеры. Недетерминированная машина Тюринга, эквивалентные определения класса NP. Сведение по Карпу. NP-полнота задачи об ограниченной остановке.

Видео