Перейти к содержимому
spiritstallion

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

Рекомендуемые сообщения

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

 

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

 

 

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

 

 

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Создайте аккаунт или войдите в него для комментирования

Вы должны быть пользователем, чтобы оставить комментарий

Создать аккаунт

Зарегистрируйтесь для получения аккаунта. Это просто!

Зарегистрировать аккаунт

Войти

Уже зарегистрированы? Войдите здесь.

Войти сейчас


  • Сейчас на странице   0 пользователей

    Нет пользователей, просматривающих эту страницу.

×