Почитал комменты. Люди, которые полазили по инету, поискали инфу и поняли, что это очередная утка, получают минусы на свои комменты. Те же, что тупо нихера не поняли и оповестили всех о своей глупости, как и те, что приняли текст на веру - получают плюсы. С каких пор глупость и тупорылый патриотизм ценятся выше здравомыслия?
Идея в том, что если найдено решение для более простой задачи, то оно будет верно и для этой же задачи, но более сложной. Поэтому сама задача обозначается P, а ее более сложная версия NP. Т.е сложнее в N раз. На деле задача может быть сложнее на порядки. Если он и вправду доказал неравенство, то это будет иметь ужасные последствия для современных методов шифрования и аутентификации. Потому, что вместо, грубо говоря, подбора пароля/ключа перебором, можно будет воспользоваться новыми методами/алгоритмами, которые сейчас считаются неэффективными и даже не рассматриваются для применения в этой сфере.
Смысл правильный, только тут не на порядки счет идет. Все гораздо хуже. NP значит "Non-Polynomial." Имеется ввиду как время счета зависит от размера задачи. Если мне нужно сложить N чисел, это можно легко сделать за N-1 операцию. То есть, если мне нужно сложить в два раза больше чисел, мне потребуется примерно в два раза больше времени. Это задача решающаяся за полиномное время. А вот классическая NP задача, задача коммивояжера, решается за N! операций. Добавив всего одну точку в задачу, решение занимает в N раз дольше. Об удвоение речи даже не идет.
В топике сказано что он доказал что P = NP )) Равенство. Да даже если дело и наоборот это привнесет ясность и в развитие криптографии будут созданы более надежные алгоритмы с учетом этого закона ))
Из Википедии -
Проблема равенства P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти?
Например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, …} есть такие, что их сумма равна 0? Ответ да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями. Следует ли отсюда, что так же легко подобрать эти числа? Кажется, что подобрать числа сложнее, но это не доказано.
...
Решение этой задачи может сделать все современные схемы шифрования устаревшими, так как шифрование заключаеться в создании настолько сложных задач, что компютеры с ними не справляются за приемлимое время. Решение P=NP теоретически должно позволить подбирать решения так же быстро, как и проверять их.
156 комментариев
11 лет назад
Удалить комментарий?
Удалить Отмена11 лет назад
Удалить комментарий?
Удалить Отмена11 лет назад
Удалить комментарий?
Удалить Отмена11 лет назад
Удалить комментарий?
Удалить Отмена11 лет назад
Удалить комментарий?
Удалить Отмена11 лет назад
Удалить комментарий?
Удалить Отмена11 лет назад
Проблема равенства P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти?
Например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, …} есть такие, что их сумма равна 0? Ответ да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями. Следует ли отсюда, что так же легко подобрать эти числа? Кажется, что подобрать числа сложнее, но это не доказано.
...
Решение этой задачи может сделать все современные схемы шифрования устаревшими, так как шифрование заключаеться в создании настолько сложных задач, что компютеры с ними не справляются за приемлимое время. Решение P=NP теоретически должно позволить подбирать решения так же быстро, как и проверять их.
Удалить комментарий?
Удалить Отмена11 лет назад
Удалить комментарий?
Удалить ОтменаУдалить комментарий?
Удалить Отмена11 лет назад
Как понимаю, это будет 101 решение.
Удалить комментарий?
Удалить Отмена11 лет назад
Удалить комментарий?
Удалить Отмена11 лет назад
Удалить комментарий?
Удалить Отмена11 лет назад
Удалить комментарий?
Удалить ОтменаУдалить комментарий?
Удалить Отмена11 лет назад
Удалить комментарий?
Удалить Отмена11 лет назад
Удалить комментарий?
Удалить Отмена11 лет назад
Удалить комментарий?
Удалить Отмена11 лет назад
Удалить комментарий?
Удалить Отмена11 лет назад
Удалить комментарий?
Удалить Отмена