Равенство классов P и NP или пароль больше не защита

[spiritstallion]

В теории алгоритмов вопрос о равенстве классов сложности P и NP является одной из центральных открытых проблем уже более трех десятилетий. Если на него будет дан утвердительный ответ, это будет означать, что теоретически возможно решать многие сложные задачи существенно быстрее, чем сейчас. http://ru.wikipedia.org/wiki/Равенство_классов_P_и_NP

 

Сотрудник с работы рассказал, что по первому каналу в новостях 16 декабря сего года показывали человека, имени его не помнит, который доказал гипотезу Пуанкаре, который получил за это миллион долларов.

 

В интернете ничего найти про этого учёного не мог. Может кто-то слышал о таком и может ли быть, что криптозащита сегодняшнего дня уйдёт в прошлое?

[Евгений Тарасов]

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

[Shadov_v]

 

 

имени его не помнит

Я так подозреваю, что это Гриша Перельман.  :D

[Format.C^]

 

 

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

Теоретически и сейчас известно, что например, подобрать к кошельку приватный ключ можно за вполне конечное время. И что, криптоалгоритм стал от этого менее надёжен? Тут просто нужно понимать, что в теории много чего возможно, но вот на практике это не применимо...

Тем более, что вопрос о равенстве классов сложности P и NP напрямую не относится к проблеме стойкости криптоалгоритмов.

[br0nevik]

Теоретическое существование "быстрого" алгоритма решения ещё не значит что он уже найден и готов к применению. Математики смешные люди -- говорят, что теоретически эту задачу просто решить, но решения не предоставляют.

 

Ну и потом, далеко не факт, что гипотеза верна.