City: Saint Petersburg Novosibirsk Kazan Language: Русский English

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

What: Lecture
When: Tuesday, 21 September 2021, 18:30–19:50
Where: Конференция в zoom, Онлайн
Slides: computationalcomplexity_lecture_210921.pdf

Description

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

Video