NP-полная задача
Математическая проблема, сложность которой растёт экспоненциально (суперэкспоненциально) и которая не поддаётся решению за полиномиальное время. Надёжность асимметричной криптографии основана на NP-полных задачах. В настоящее время в основном используется две: проблема дискретного логарифмирования в конечном поле и проблема разложения на множители больших чисел. Если какая-либо из них станет решаема за полиномиальное время, соответствующие криптосистемы потеряют свою нынешнюю стойкость.
NP-задачей (недетерминированно полиномиальной задачей) называется задача, у которой за полиномиальное время можно проверить решение. (Название происходит от того, что на недетерминированных машинах (гипотетических машинах, обладающих неогранниченным числом процессоров) такие задачи решаются за полиномиальное время.)
NP-полной называется задача, к которой за полиномиальное время можно свести решение любой NP-задачи.
Нахождение алгоритма, решающего какую-либо NP-полную задачу за полиномиальное время позволит находить решения NP-задач за полиномиальное время, то есть позволит считать их P-задачами.
Равны ли классы задач P и NP – до сих пор не решённая математическая проблема.
( за решение которой обещан приз в миллион долларов :)
http://www.kinnet.ru/cterra/626/252819.html
Не совсем понятно, почему тогда за решенеи данных задач обещан такой большой приз.
А если решена одна из таких задач за n шагов с помощью специально разработанного сопроцессора, то уже не дается приз? Ведь может выясниться, что на полученном принцепе могут решаться все NP-полные задачи.
Слишком общо сказано. А может быть NP-полных задач в указанном смысле вообще не существует?! А вообще, странная фраза сама по себе. Допустим, NP-полная задача – очень-очень сложная, и тогда сводя NP-задачу к NP-полной я переусложня алгоритм, достаточно лишь его переусложнять так чтобы метод работал на всех NP-задачах.
P. S.: ещё с института ненавижу математиков за их больную на голову логику и полнейшее отсутствие давать понятные определения, жертвы понятностью в пользу большей логической корректности, а также клиническому не понимаю эффекта "за деревьями леса не видно".
Если выясниться принцип – получите! :)
Ответ на этот вопрос дал Стивен Кук в 1971-м году, доказав (теорема Кука), что некоторая конкретная задача, а именно задача выполнимости булевых формул, NP-полна.
при переусложнении важно не потерять полиномиальность сводимости.
Вот вам "лес":
Существуют ли (полиномиально) необратимые (полиномиальные) функции?
или,
Существуют ли задачи с быстро(=полиномиально) проверяемым ответом, который нельзя быстро найти?
Н. П. Варновский. Проблема P =? NP, классы сложностей и криптография