Jump to content
spiritstallion

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

Recommended Posts

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

 

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

 

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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

 

 

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

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

Share this post


Link to post
Share on other sites

 

 

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

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

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

Share this post


Link to post
Share on other sites

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

 

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...