Структурная теория сложности
Курс Хит![](https://www.lektorium.tv/sites/lektorium.tv/files/courses/1283292543_22750_1269596530_12794_c9_l7.flv_002869033.jpg)
Структурная теория сложности изучает классы вычислительных задач и взаимоотношения между ними. Эта область информатики содержит как «великие'' нерешенные задачи (например, P vs NP — одна из семи задач, за решение которых Clay Mathematical Institute объявил призы по $1,000,000), так и красивые теоремы (теорема Шамира об интерактивных доказательствах, теорема Разборова о монотонных логических схемах…). Без знания теории сложности невозможно глубокого понимания криптографии и многих других областей теоретической информатики.
Лекции курса
8