Структурная теория сложности

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