Абрамов С. А. - Сложность алгоритмов - Полиномиальные языки

00:02:07 1. Машина Тьюринга (МТ) 00:05:54 2. Полиномиальная МТ 00:13:55 3. Оценка сложности алгоритма МТ 00:19:25 4. Полиномиальные языки 00:21:23 5. Утверждение о сведении полиномиальных языков 00:36:25 6. Язык выполнимости 00:39:20 7. Язык Клика 00:48:57 8. Сведение языка выполнимости к языку Клика 00:58:37 9. Класс NP языков, распознаваемых за полиномиальное время 01:02:00 10. Утверждение о принадлежности класса 01:11:50 11. Определение полноты и трудности языка 01:13:25 12. Утверждение о NP языках 01:19:52 13. К-выполнимость