Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dubna/2008/courses/pritykin.htm
Дата изменения: Sun Jun 8 22:34:42 2008
Дата индексирования: Sat Sep 6 18:53:12 2008
Кодировка: koi8-r
Поисковые слова: spacecraft
Dubna-2008: Pritykin
На главную страницу ЛШСМ-2008 К списку курсов ЛШСМ-2008

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

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

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

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

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

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

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