Перейти к содержанию

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


spiritstallion

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

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

 

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

 

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

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

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

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

 

 

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

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

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

 

 

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

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

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

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

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

 

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

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

Для публикации сообщений создайте учётную запись или авторизуйтесь

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

Создать учетную запись

Зарегистрируйте новую учётную запись в нашем сообществе. Это очень просто!

Регистрация нового пользователя

Войти

Уже есть аккаунт? Войти в систему.

Войти
  • Последние посетители   0 пользователей онлайн

    • Ни одного зарегистрированного пользователя не просматривает данную страницу
  • Similar Topics

×
×
  • Создать...