Решена задача равенства классов P=NP! Будет ли крах системы сохранности данных?

[listik]

Немного теории: Задача  P=NP относится к так называемым "Задачам тысячелетия"(Millennium Prize Problems), за решение которых удосуживаютс нобелевской премии. В настоящее время только одна из семи проблем тысячелетия (гипотеза Пуанкаре) решена. Филдсовская премия за её решение была присуждена Григорию Перельману, который отказался от неё.

В теории алгоритмов вопрос о равенстве классов сложности P и NP является
одной из центральных открытых проблем уже более трех десятилетий. Если на
него будет дан утвердительный ответ, это будет означать, что теоретически
возможно решать многие сложные задачи существенно быстрее, чем сейчас.

Классы P и NP
В конечном счете проблема P=NP состоит в следующем: если положительный
ответ на какой-то вопрос можно быстро проверить (за полиномиальное время),
то правда ли, что ответ на этот вопрос можно быстро найти (за
полиномиальное время и используя полиномиальную память)?

Проще говоря, действительно ли задачу легче проверить, чем решить!


Однако... Челябинским математиком, Анатолием Васильевичем Панюковым, было получено строгое математическое дoказательство. И это - опять нобелевская премия, как и за дoказательство теоремы Пуанкаре!
Так вот, про дoказательство P=NP. Почти вся криптография основана на так называемых "необратимых функциях" (P"не равно"NP). Под этим имеют в виду функцию, для которой известен полиномиальный алгоритм вычисления, а для вычисления обратной функции такого алгоритма не найдено. На предположении, что такого алгоритма вообще нет, основана надежда на надежность многих шифров и защитных систем. дoказательство равенства P=NP поставит под удар алгоритмы криптографии, надежность многих шифров и защитных систем хранения конфидециальной информации.

Кому интересно, вот так выглядит список Задач тысячелетия:
Равенство классов P и NP (догазательство разослано для проверки)
Гипотеза Ходжа
Гипотеза Пуанкаре (дoказана)
Гипотеза Римана
Теория Янга — Миллса
Существование и гладкость решений уравнений Навье — Стокса
Гипотеза Бёрча — Свиннертон-Дайера

[beyond]

а гречка подорожает?

[listik]

а гречка подорожает?

Юмор оценил. 

Просто дoказательство P=NP приведет к тому, что пароли не надо будет подбирать для взлома долго и нудно методом перебора, а возможно будет банaльно-строгое решение этой задачи...

[beyond]

.если это случиться, то это ЭТО сильно изменит отношение к информации....
если честно, то я  бы этого очень не хотел так же как и восстaние терминаторов )

[listik]

.если это случиться, то это ЭТО сильно изменит отношение к информации....
если честно, то я  бы этого очень не хотел так же как и восстaние терминаторов )

Помимо такого косяка с криптозащитой есть и положительные моменты - будут решены множества задач, которые решались лишь методом перебора. Выбор оптимума из области дискретных решений и т.д.
А вот восстaния терминаторов - это нам не надо.
Хочу пошутить по случаю - Сноуден вовремя успел. Вот как сейчас не станет паролей и тайн...

[Sevab]

Не обязательно все из представленных задач в принципе решаемы.
Возможно некоторые из них больше философские типа "Камень чувствует или не чувствует? Но он ведь чувствует, что ничего не чувствует?". Или "Может ли господь создать камень, который он не сможет поднять?" и т.д.

Так что возможно паника преждевременна . Будем опираться на факты (т.е. уже дoказанные теоремы).

Равенство классов P и NP (догазательство разослано для проверки)

Подождем, что скажут проверяющие. Возможно мыльный пузырь. Если нет, тогда паникуем.

[listik]

Так что возможно паника преждевременна . Будем опираться на факты (т.е. уже дoказанные теоремы).
Подождем, что скажут проверяющие. Возможно мыльный пузырь. Если нет, тогда паникуем.

Конечно подождем. А что еще остается? Кстати эту задачу (равенство классов) уже несколько раз пытались решить и представляли дoказательство (по моему в 2002 и в 2007). Но... Не прокатило! 

[Гарик+]

Вы, профессор, воля ваша, что-то нескладное придумали! Оно, может, и умно, но больно непонятно. Над вами потешаться будут. (с)   

[listik]

Вы, профессор, воля ваша, что-то нескладное придумали! Оно, может, и умно, но больно непонятно. Над вами потешаться будут. (с)   

Аргументируйте цитатку, товариСЧ!

[Гарик+]

А зачем? Помните Аркадий Аполлонович Семплеяров тоже захотел разоблачений и вон что из этого вышло..