| What: | Lecture |
| When: | Thursday, 15 September 2016, 18:30–19:50 |
| Where: | ПОМИ РАН |
Определение класса NP, примеры. Доказательство простоты числа (критерий Пратта). Сведения и полнота. NP-полнота задачи об ограниченной остановке. Сведение Circuit-SAT к 3SAT.
