| What: | Lecture |
| When: | Tuesday, 21 September 2021, 18:30–19:50 |
| Where: | Конференция в zoom, Онлайн |
| Slides: | computationalcomplexity_lecture_210921.pdf |
Включение P в P/poly. Эффективная система доказательств. Класс NP, примеры. Недетерминированная машина Тюринга, эквивалентные определения класса NP. Сведение по Карпу. NP-полнота задачи об ограниченной остановке.
