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

YoBit.Net

Фотография

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


  • Авторизуйтесь для ответа в теме
Сообщений в теме: 4

#1 spiritstallion

spiritstallion

    Пользователь

  • Пользователи
  • PipPip
  • 182 сообщений

Отправлено 17 December 2013 - 16:50

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

 

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

 

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


  • 0

Слава России! Россия - это все славянские народы!


#2 Евгений Тарасов

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

    Форумный сумасшедший

  • Пользователи
  • PipPipPip
  • 1105 сообщений

Отправлено 17 December 2013 - 17:05

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


  • 0

#3 Shadov_v

Shadov_v

    Пользователь

  • Пользователи
  • PipPip
  • 82 сообщений

Отправлено 17 December 2013 - 17:42

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

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


  • 1

#4 Format.C^

Format.C^

    Primus inter pares

  • Супермодераторы
  • 3176 сообщений
  • ГородХарьков

Отправлено 17 December 2013 - 21:40

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

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

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


  • 0

Не зная покоя и отдыха, при лунном и солнечном свете мы делаем деньги из воздуха, чтоб после спустить их на ветер!

 


#5 bronevik

bronevik

    Продвинутый пользователь

  • Bits.media Team
  • PipPipPip
  • 1500 сообщений
  • ГородМосква

Отправлено 19 December 2013 - 13:25

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

 

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


  • 0

1BTCSECFkk7pornT7FhmUkBzuY4PrzT6cM
 

- Сотня кварков это сотня кварков.

- Но не когда цена две сотни кварков и не когда у тебя на кошельке бюджет Либерии. Дай-ка пощупать как хрустят твои койны





Количество пользователей, читающих эту тему: 0

0 пользователей, 0 гостей, 0 анонимных