January 2019

M T W T F S S
 123456
78 910111213
14 151617181920
21222324252627
28293031   

За стиль благодарить

Развернуть метки

No cut tags
Tuesday, January 7th, 2014 05:31 pm
Пока народ плюется на "Шерлока", я с большим запозданием стал смотреть Elementary и практически сразу (2 серия 2 сезона) заторчал: сюжет вращается вокруг открытия группой математиков (точнее, несколькими группами) того факта, что проблема "равны ли классы сложности P и NP" имеет положительное решение (фантастическое допущение).

- при этом в фильме дается понятное среднему зрителю сериального мыла определение проблемы: "верно ли, что любая задача, решение которой компьютер может БЫСТРО ПРОВЕРИТЬ, может также быть БЫСТРО РЕШЕНА";

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

Мне лично кажется. что правдоподобнее было бы, если бы решение оказалось ложно-положительным, то есть удалось бы доказать P для некоторых конкретных NP задач и вскрыть общепринятые шифры, но не в общем случае, но сценаристы решили не переусложнять. Я все равно в восторге.
Tuesday, January 7th, 2014 02:10 pm (UTC)
Я чуть-чуть связан с этой проблемой (мой научный руководитель ей занимался), так что мне стало очень интересно. Что это за сериал такой?
Tuesday, January 7th, 2014 02:58 pm (UTC)
Американский современный Шерлок, второй сезон идет как раз сейчас в США, первый, кажется, шел и у нас (по "Домашнему") в прошлом году. Мне в целом нравится, актеры стильные и вообще. На Рутрекере ищете по слову Elementary, есть статья в англ. и русской википедии.
Tuesday, January 7th, 2014 02:20 pm (UTC)
Совпадение множеств п и нп - это не фантастическое предположение, это реальный вопрос.
Tuesday, January 7th, 2014 02:38 pm (UTC)
Вопрос-то реальный, но много ли есть серьезных специалистов, верящих, что P=NP?
Tuesday, January 7th, 2014 02:44 pm (UTC)
Это отличие научного знания от ненаучного. Не важно, какой специалист во что верит. Важно от чего отталкивается, и на что опирается.
Tuesday, January 7th, 2014 02:47 pm (UTC)
Я думал, в общепринятых шифрах задачи NP-полны (раз уж ты не можешь доказать, что шифр твой невскрываемый, можно по крайней мере доказать, что он не хуже других).
Tuesday, January 7th, 2014 03:29 pm (UTC)
Да вроде нет (разложение на простые множители разве NP-полно?).
Tuesday, January 7th, 2014 04:10 pm (UTC)
разложение на множители неизвестно, полно или нет (и есть подозрения, что нет, потому что оно решается "на квантовых компьютерах", а про полные задачи это неизвестно)
Tuesday, January 7th, 2014 02:52 pm (UTC)
Прелесть NP-полноты именно в том, что решение любой из NP-полных задач даёт решение и всех остальных.
[Хотя, кончено, «полиномиальность» это замечательно, но степень у полинома может быть разной. Скажем, если это «полиномиальное время» — O(n^1000), непосредственного практического значения такое доказательство P=NP иметь не будет :-) (но, конечно, всё равно растрясёт «основы» изрядно)]
(Ну и что до «потенциальных убытков» — «потенциальные прибытки» тоже отнюдь не ограничиваются «премией математического сообщества». К тому же, если до решения вообще возможно додуматься, то закрывать тему толку мало, всё равно где-то ещё вылезет, и весьма скоро. Хотя, «казалось бы умных идиотов» в мире полно, из недавнего можно NSA посмотреть; полностью спускать в унитаз наработанное за десятки лет доверие, и ради весьма жалких краткосрочных результатов [Dual EC DRBG], что может быть безумнее?)
Tuesday, January 7th, 2014 05:26 pm (UTC)
> доказать P для некоторых конкретных NP задач

Занудно. P по определению подмножество NP, так что доказательство этого факта тривиально. Например путем приведения примера P-задачи.

То есть тут либо уж надо доказывать про NP-полные задачи, но тогда P=NP,либо, и это наиболее правдоподобное предположение, для задачи для которой не известно ни NP-полнота ни P, доказать ее полиномиальность. Но теряется вау фактор для кино ;)

Либо идти в еще более изотерические классы под NP (например пересечение NP b co-NP) и доказавать что они совпадают с P. Что было бы правдоподобно, но еще сложнее.

Wednesday, January 8th, 2014 04:28 am (UTC)
Насколько я знаю, ни один из известных шифров не использует того, что P!=NP.
В 70е, вскоре после изобретения RSA, была попытка сделать шифрование с публичным ключом на основе NP-полных задач, но она провалилась, потому что большинство рандомных данных для NP-задачи решаются жадным алгоритмом, а данные, на которых требуется честный перебор, автоматически и не сгенерируешь.
Thursday, January 9th, 2014 10:37 pm (UTC)
Это почему-то было модно в прошлом сезоне. Ср.
Thursday, January 9th, 2014 11:04 pm (UTC)
Ого.

Поневоле станешь конспирологом. Ну или сценаристы вместе выпивают:-)