Юрий Львович Притыкин

Что такое проблема P vs. NP ?

Ю.Л.Притыкин планирует провести 4 занятия

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

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

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

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

Organization Committee e-mail:
dubna@mccme.ru