Решение данного равенства позволит ускорить решение оптимизационных задач в бизнесе и на производстве, которые на данный момент занимают более года. Более точное и быстрое решение этих задач позволит увеличить прибыль и сократить издержки тем предприятиям, которые использую программное обеспечение для решения такого рода задач.
Где-то здесь подвох: какой смысл решать задачу без проверки? Ну, нагенерируешь ты случайных чисел, а потом космические корабли будут падать на головы народа. Зато ведь как круто: посчитал быстрей, чем проверил!!!
Потрясающе, в списке доказательств, уже больше ста вариантов. Причем уверенно некоторые доказывают равенство, некоторые также уверенно доказывают неравенство. Два автора вообще утверждают, что равенство (неравенство) недоказуемо.
Например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, …} есть такие, что их сумма равна 0 (задача о суммах подмножеств)? Ответ да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями (информация, необходимая для проверки положительного ответа, называется сертификатом). Следует ли отсюда, что так же легко подобрать эти числа? Проверить сертификат так же легко, как найти его? Кажется, что подобрать числа сложнее, но это не доказано.
P - это те задачи, которые решаются за полиномиальное время и естественно проверяются.
NP - те задачи, которые можно решить перебором, т.е. за экспоненциальное время, и проверить за полиномиальное.
А вот можно ли решить эти переборные задачи из класса NP за полиномиальное время - вот в чем вопрос. Гениальная проблема: интуиция подсказывает, что нельзя, а формального доказательства нет.
А кто-то вообще предлагает доказательства равенства. Поскольку NP задач довольно много (несколько сотен известно, если не ошибся), и они друг к другу сводятся за полиномиальное время, то достаточно решить одну, чтобы решить их все без квантовых компьютеров и прочей алхимии.
из той же вики выше: «Если на него будет дан утвердительный ответ, это будет означать, что теоретически возможно решать многие сложные задачи существенно быстрее, чем сейчас.» Где именно накроется криптография? она и так периодически местами накрывается когда находят способ ускорения расшифровки...
например обычный паяльник резко сокращает время на перебор паролей, так и свой паяльник и для остального найдут
RSA — всего лишь одна из многих систем открытого распределения ключей, и всего лишь одна из немногих систем выработки ЭЦП.
Кроме того, любая уважающая себя криптосистема поддерживает набор различных алгоритмов. Исключения, составляют системы, подверженные регулированию. Но это отдельный разговор.
Интересно, что для серьезных нужд RSA никогда и не пользовались. Буржуи пользовались DSA, мы пользовались ГОСТ. Давным-давно, что тот, что другой — эллиптический.
RSA широко используется в TLS, но гипотетическая атака на шифротекст RSA (которая еще и не факт что будет эффективной) при доказательстве P=NP, не приведет к тому что перехваченные TLS-потоки можно будет расшифровать.
Появится только уязвимость к man-in-the-middle атакам. На практике, это означает всего лишь ликвидацию всех существующих доверенных сертификатов ЦС. Но это — головная боль ЦС. На практике, эффективность MitM-атак вызывает очень и очень серьезные сомнения.
занимался поисками решения одной из сложнейших актуальных задач тысячелетия – равенства классов P и NP одной из сложнейших актуальных задач тысячелетия
реально что ли? самая наиактуальнейшая задача тысячелетия?