Проблема «P vs. NP» (равны ли P и NP) является одной из фундаментальных проблем теоретической информатики (theoretical computer science) и математики вообще, что подтверждается и разными внематематическими формальностями (например, это одна из семи «проблем тысячелетия», за решение каждой из которых присуждён приз в 1млн. долларов).

В курсе будет рассказано, в чём заключается формулировка проблемы, а также о разных понятиях и результатах вокруг неё. Никаких особых предварительных знаний не требуется.

Примерная программа курса:

1. Неформальные разговоры. Формализация понятия вычисления: машины Тьюринга.
2. Задачи, которые быстро решаются, и задачи, в которых можно быстро проверить ответ: классы P и NP.
   P vs. NP и другие нерешённые проблемы теории сложности вычислений.
3. Самые сложные задачи в классе NP: полиномиальная сводимость и NP-полнота.
4. Быстрые приближённые решения задач, которые сложно решить точно: вероятностные и приближённые алгоритмы.