Electric_Gypsy
Newbie | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Это одна из "задач тысячелетия" (по версии института Клэя).
Фишка в том, что есть класс p-задач, для которых существуют полиномиальные (по времени) алгоритмы решения. И класс np-задач, ответ для которых можно проверить за полиномиальное время, а решаются они за экспоненциальное время (перебор или brute force). Для некоторых np-задач найдены полиномиальные алгоритмы решения, но не для всех. Есть так же класс np-полных задач, к которым можно свести все остальные np-задачи. Значит, если для одной np-полной задачи будет найден полиномиальный алгоритм решения, то можно будет решить все np-задачи, которые сводятся к ней, за это же время.
Это важно так же и в практическом плане, поскольку в криптографических алгоритмах при шифровке исходят из того, что на взлом тратится экспоненциальное время, а не полиномиальное, и соответственно подбирают длину шифра.
Для np-полных задач не найден полиномиальный алгоритм решения, и так же не известно, существует ли он вообще. Институт Клэя заплатит $1мио за такой алгоритм либо за доказательство, что его нет. Есть так же вариант, что в существующих аксиомах ничего нельзя доказать, и треть ученых склоняются к такому варианту. Но за доказательство этого последнего варианта ничего не заплатят.
Сапер относится к классу np-полных задач. |
Всего записей: 21 | Зарегистр. 04-03-2008 | Отправлено: 20:44 31-05-2010 | Исправлено: Electric_Gypsy, 20:53 31-05-2010 |
|
