Задача разрешения вопроса о (не)равенстве классов P и NP временной сложности вычислительных задач поставлена С. Смейлом (1998 г.) третьей в список важнейших математических проблем 21-ого века.
Институт Клея определил ей третье место в <<списке математических задач третьего тысячелетия>> (http://www.claymath.org/millennium-problems).
Вопрос, поставленный в задаче, можно понимать так:
<<Для каждой ли задачи поиска объекта с данным разумным свойством, посредством исчерпывающего перебора, существует разумно быстрый алгоритм поиска этого объекта?>>
Я расскажу о формальной постановке задачи и, связанных с ней, понятиях теории сложности вычислений. Приведу причины, связывающие важность ответа, на поставленный в задаче вопрос, с разработкой квантовых компьютеров и новых теоретических (воображаемых) моделей вычислений.