Структурная теория сложности изучает классы вычислительных задач и взаимоотношения между ними. Эта область информатики содержит как "великие" нерешенные задачи (например, P vs NP — одна из семи задач, за решение которых Clay Mathematical Institute объявил призы по $1,000,000), так и красивые теоремы (теорема Шамира об интерактивных доказательствах, теорема Разборова о монотонных логических схемах…). Без знания теории сложности невозможно глубокого понимания криптографии и многих других областей теоретической информатики.

Конспекты лекций, читавшихся ранее: http://logic.pdmi.ras.ru/~hirsch/students/complexity1/

Видео лекций https://www.lektorium.tv/course/22750?id=22750