"P=NP и социальные последствия этого факта"

[taki_net]

Пока народ плюется на "Шерлока", я с большим запозданием стал смотреть Elementary и практически сразу (2 серия 2 сезона) заторчал: сюжет вращается вокруг открытия группой математиков (точнее, несколькими группами) того факта, что проблема "равны ли классы сложности P и NP" имеет положительное решение (фантастическое допущение).

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

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

Мне лично кажется. что правдоподобнее было бы, если бы решение оказалось ложно-положительным, то есть удалось бы доказать P для некоторых конкретных NP задач и вскрыть общепринятые шифры, но не в общем случае, но сценаристы решили не переусложнять. Я все равно в восторге.

Comments

[chaotickgood.livejournal.com]

Я чуть-чуть связан с этой проблемой (мой научный руководитель ей занимался), так что мне стало очень интересно. Что это за сериал такой?

[taki-net.livejournal.com]

Американский современный Шерлок, второй сезон идет как раз сейчас в США, первый, кажется, шел и у нас (по "Домашнему") в прошлом году. Мне в целом нравится, актеры стильные и вообще. На Рутрекере ищете по слову Elementary, есть статья в англ. и русской википедии.

[pssshik.livejournal.com]

Совпадение множеств п и нп - это не фантастическое предположение, это реальный вопрос.

[xgrbml.livejournal.com]

Вопрос-то реальный, но много ли есть серьезных специалистов, верящих, что P=NP?

[pssshik.livejournal.com]

Это отличие научного знания от ненаучного. Не важно, какой специалист во что верит. Важно от чего отталкивается, и на что опирается.

[vmgor.livejournal.com]

Я думал, в общепринятых шифрах задачи NP-полны (раз уж ты не можешь доказать, что шифр твой невскрываемый, можно по крайней мере доказать, что он не хуже других).

[xgrbml.livejournal.com]

Да вроде нет (разложение на простые множители разве NP-полно?).

нет,

[a-shen.livejournal.com]

разложение на множители неизвестно, полно или нет (и есть подозрения, что нет, потому что оно решается "на квантовых компьютерах", а про полные задачи это неизвестно)

[laruldan]

Прелесть NP-полноты именно в том, что решение любой из NP-полных задач даёт решение и всех остальных.
[Хотя, кончено, «полиномиальность» это замечательно, но степень у полинома может быть разной. Скажем, если это «полиномиальное время» — O(n^1000), непосредственного практического значения такое доказательство P=NP иметь не будет :-) (но, конечно, всё равно растрясёт «основы» изрядно)]
(Ну и что до «потенциальных убытков» — «потенциальные прибытки» тоже отнюдь не ограничиваются «премией математического сообщества». К тому же, если до решения вообще возможно додуматься, то закрывать тему толку мало, всё равно где-то ещё вылезет, и весьма скоро. Хотя, «казалось бы умных идиотов» в мире полно, из недавнего можно NSA посмотреть; полностью спускать в унитаз наработанное за десятки лет доверие, и ради весьма жалких краткосрочных результатов [Dual EC DRBG], что может быть безумнее?)

[marknn.livejournal.com]

> доказать P для некоторых конкретных NP задач

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

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

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

[pargentum.livejournal.com]

Насколько я знаю, ни один из известных шифров не использует того, что P!=NP.
В 70е, вскоре после изобретения RSA, была попытка сделать шифрование с публичным ключом на основе NP-полных задач, но она провалилась, потому что большинство рандомных данных для NP-задачи решаются жадным алгоритмом, а данные, на которых требуется честный перебор, автоматически и не сгенерируешь.

[tacente.livejournal.com]

Это почему-то было модно в прошлом сезоне. Ср.

[taki-net.livejournal.com]

Ого.

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