Пока народ плюется на "Шерлока", я с большим запозданием стал смотреть Elementary и практически сразу (2 серия 2 сезона) заторчал: сюжет вращается вокруг открытия группой математиков (точнее, несколькими группами) того факта, что проблема "равны ли классы сложности P и NP" имеет положительное решение (фантастическое допущение).
- при этом в фильме дается понятное среднему зрителю сериального мыла определение проблемы: "верно ли, что любая задача, решение которой компьютер может БЫСТРО ПРОВЕРИТЬ, может также быть БЫСТРО РЕШЕНА";
- вполне корректно описывается, что будет, если решение положительное: спец по инфобезопасности говорит "миллионная премия математического общества - ничто по сравнению с масштабов прибылей и убытков в нашей отрасли - придется менять все системы шифрования, используемые в данный момент, а инсайдеры смогут в течение некоторого времени взломать всё".
Мне лично кажется. что правдоподобнее было бы, если бы решение оказалось ложно-положительным, то есть удалось бы доказать P для некоторых конкретных NP задач и вскрыть общепринятые шифры, но не в общем случае, но сценаристы решили не переусложнять. Я все равно в восторге.
- при этом в фильме дается понятное среднему зрителю сериального мыла определение проблемы: "верно ли, что любая задача, решение которой компьютер может БЫСТРО ПРОВЕРИТЬ, может также быть БЫСТРО РЕШЕНА";
- вполне корректно описывается, что будет, если решение положительное: спец по инфобезопасности говорит "миллионная премия математического общества - ничто по сравнению с масштабов прибылей и убытков в нашей отрасли - придется менять все системы шифрования, используемые в данный момент, а инсайдеры смогут в течение некоторого времени взломать всё".
Мне лично кажется. что правдоподобнее было бы, если бы решение оказалось ложно-положительным, то есть удалось бы доказать P для некоторых конкретных NP задач и вскрыть общепринятые шифры, но не в общем случае, но сценаристы решили не переусложнять. Я все равно в восторге.
no subject
no subject
no subject
no subject
no subject
no subject
no subject
нет,
no subject
[Хотя, кончено, «полиномиальность» это замечательно, но степень у полинома может быть разной. Скажем, если это «полиномиальное время» — O(n^1000), непосредственного практического значения такое доказательство P=NP иметь не будет :-) (но, конечно, всё равно растрясёт «основы» изрядно)]
(Ну и что до «потенциальных убытков» — «потенциальные прибытки» тоже отнюдь не ограничиваются «премией математического сообщества». К тому же, если до решения вообще возможно додуматься, то закрывать тему толку мало, всё равно где-то ещё вылезет, и весьма скоро. Хотя, «казалось бы умных идиотов» в мире полно, из недавнего можно NSA посмотреть; полностью спускать в унитаз наработанное за десятки лет доверие, и ради весьма жалких краткосрочных результатов [Dual EC DRBG], что может быть безумнее?)
no subject
Занудно. P по определению подмножество NP, так что доказательство этого факта тривиально. Например путем приведения примера P-задачи.
То есть тут либо уж надо доказывать про NP-полные задачи, но тогда P=NP,либо, и это наиболее правдоподобное предположение, для задачи для которой не известно ни NP-полнота ни P, доказать ее полиномиальность. Но теряется вау фактор для кино ;)
Либо идти в еще более изотерические классы под NP (например пересечение NP b co-NP) и доказавать что они совпадают с P. Что было бы правдоподобно, но еще сложнее.
no subject
В 70е, вскоре после изобретения RSA, была попытка сделать шифрование с публичным ключом на основе NP-полных задач, но она провалилась, потому что большинство рандомных данных для NP-задачи решаются жадным алгоритмом, а данные, на которых требуется честный перебор, автоматически и не сгенерируешь.
no subject
no subject
Поневоле станешь конспирологом. Ну или сценаристы вместе выпивают:-)