id: Гость   вход   регистрация
текущее время 11:28 28/03/2024
Владелец: SATtva (создано 14/09/2006 22:50), редакция от 27/08/2006 21:16 (автор: SATtva) Печать
Категории: криптография
создать
просмотр
редакции
ссылки

NP-полная задача


Математическая проблема, сложность которой растёт экспоненциально (суперэкспоненциально) и которая не поддаётся решению за полиномиальное время. Надёжность асимметричной криптографии основана на NP-полных задачах. В настоящее время в основном используется две: проблема дискретного логарифмирования в конечном поле и проблема разложения на множители больших чисел. Если какая-либо из них станет решаема за полиномиальное время, соответствующие криптосистемы потеряют свою нынешнюю стойкость.


 
— Гость (13/11/2006 00:30)   <#>
P-задачей (полиномиальной задачей) называется задача, у которой за полиномиальное (от длинны входа) время можно найти решение.

NP-задачей (недетерминированно полиномиальной задачей) называется задача, у которой за полиномиальное время можно проверить решение. (Название происходит от того, что на недетерминированных машинах (гипотетических машинах, обладающих неогранниченным числом процессоров) такие задачи решаются за полиномиальное время.)

NP-полной называется задача, к которой за полиномиальное время можно свести решение любой NP-задачи.

Нахождение алгоритма, решающего какую-либо NP-полную задачу за полиномиальное время позволит находить решения NP-задач за полиномиальное время, то есть позволит считать их P-задачами.

Равны ли классы задач P и NP – до сих пор не решённая математическая проблема.

( за решение которой обещан приз в миллион долларов :)

http://www.kinnet.ru/cterra/626/252819.html
— Гость (13/11/2006 01:44)   <#>
Короче, NP-полными называются задачи, к которым задачи с полиномиально проверямыми ответами сводятся полиномиально!
— Vera (24/04/2008 12:51)   <#>
"Если какая-либо из них станет решаема за полиномиальное время, соответствующие криптосистемы потеряют свою нынешнюю стойкость."

Не совсем понятно, почему тогда за решенеи данных задач обещан такой большой приз.

А если решена одна из таких задач за n шагов с помощью специально разработанного сопроцессора, то уже не дается приз? Ведь может выясниться, что на полученном принцепе могут решаться все NP-полные задачи.
— Гость (25/04/2008 04:04)   <#>
NP-полной называется задача, к которой за полиномиальное время можно свести решение любой NP-задачи.

Слишком общо сказано. А может быть NP-полных задач в указанном смысле вообще не существует?! А вообще, странная фраза сама по себе. Допустим, NP-полная задача – очень-очень сложная, и тогда сводя NP-задачу к NP-полной я переусложня алгоритм, достаточно лишь его переусложнять так чтобы метод работал на всех NP-задачах.

P. S.: ещё с института ненавижу математиков за их больную на голову логику и полнейшее отсутствие давать понятные определения, жертвы понятностью в пользу большей логической корректности, а также клиническому не понимаю эффекта "за деревьями леса не видно".
— Гость (25/04/2008 16:37)   <#>
Не совсем понятно, почему тогда за решенеи данных задач обещан такой большой приз.
Приз обещан не за решение, а за выяснение возможности такого решения. И ответ может быть отрицательным. Но вообще-то это задача теоретическая.

может выясниться, что на полученном принцепе могут решаться все NP-полные задачи.
Если выясниться принцип – получите! :)

А может быть NP-полных задач в указанном смысле вообще не существует?
Ответ на этот вопрос дал Стивен Кук в 1971-м году, доказав (теорема Кука), что некоторая конкретная задача, а именно задача выполнимости булевых формул, NP-полна.

достаточно лишь его переусложнять так чтобы метод работал на всех NP-задачах
при переусложнении важно не потерять полиномиальность сводимости.

"за деревьями леса не видно".

Вот вам "лес":
Существуют ли (полиномиально) необратимые (полиномиальные) функции?
или,
Существуют ли задачи с быстро(=полиномиально) проверяемым ответом, который нельзя быстро найти?
— Гость (25/04/2008 23:05)   <#>
К моменту возникновения теории -полноты в математике было известно довольно много задач, которые решались тривиальным перебором за экспоненциальное время, и для которых не удалось найти полиномиальные алгоритмы. Для большинства этих задач относительно быстро и несложно была установлена NP-полнота (или NP-трудность). В некоторых случаях доказательство NP-полноты потребовало определенных усилий. Были и такие примеры, когда попытки доказательства NP-полноты не увенчались успехом, и в конце концов было доказано, что задача принадлежит классу P (как в случае задачи линейного программирования). А несколько задач, как говорится, "повисли". Самые известные из них – факторизация, дискретное логарифмирование и изоморфизм графов.

Вычислительная сложность задач факторизации и дискретного логарифмирования интересна прежде всего для криптографии. Но речь идет вовсе не о NP-полноте. NP-полнота – это сложность только "в худшем случае", для криптографии слишком слабая. Более важная и трудная задача – обосновать, что функция RSA и дискретная экспонента являются односторонними функциями.
Н. П. Варновский. Проблема P =? NP, классы сложностей и криптография
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3