Сложность вычислений 2. Классы P и NP

0:00:00 - Начало лекции
0:01:12 - классы P и DTIME
0:07:48 - примеры задач из класса P
0:17:38 - PLANAR, критерий Вагнера
0:29:26 - теория Робертсона-Сеймура
0:36:57 - квазиполиномы
0:44:10 - сложностные классы
0:48:40 - определение NP(сертификатное)
0:54:13 - примеры задач NP
1:05:13 - P вложен в NP
1:08:47 - определение NP (через недетерминированную машину Тьюринга)
1:13:41 - эквивалентность определений NP

Лекция от 11.09.2019

Лектор: Д.В. Мусатов

Снимала: Александра Погребная
Монтировала: Татьяна Миллер

Видео Сложность вычислений 2. Классы P и NP канала Лекторий ФПМИ