Заседание No. 35, P vs. NP (элементарные понятия проблемы перебора)

Докладчик: Андрей Петрович Немытых (ИПС им. А.К. Айламазяна РАН)
Дата: 2 октября 2015
Время: 13:00
Место: зал ученого совета ИПС
Аннотация:

Задача разрешения вопроса о (не)равенстве классов P и NP временной сложности вычислительных задач поставлена С. Смейлом (1998 г.) третьей в список важнейших математических проблем 21-ого века.

Институт Клея определил ей третье место в <<списке математических задач третьего тысячелетия>> (http://www.claymath.org/millennium-problems).

Вопрос, поставленный в задаче, можно понимать так:
<<Для каждой ли задачи поиска объекта с данным разумным свойством, посредством исчерпывающего перебора, существует разумно быстрый алгоритм поиска этого объекта?>>

Я расскажу о формальной постановке задачи и, связанных с ней, понятиях теории сложности вычислений. Приведу причины, связывающие важность ответа, на поставленный в задаче вопрос, с разработкой квантовых компьютеров и новых теоретических (воображаемых) моделей вычислений.