[HELL_YEAH!!1] P=NP

Опа, привет мои «криптостойкие"алгоритмы? =)

На этот раз RLY?

В очередной раз?

RSA-капец

Ну может и нет. Хотя ему уже много бабок отвалили. Видимо это конец. Теперь сони уже никто не спасет.

Бразильцы говорят что да.

Опа, привет мои «пять лет проверки научным сообществом, ещё сотня статей и три года устранения недочётов».

Причём тут тётя Sony? Я из криокамеры...

А вроде ж P!=NP и по другому быть не может, просто доказать пока никто не мог.

я в этом не специалист, но разве доказательство того, что ОДНА из задач из P также взодит в NP, доказывает то, что ВСЕ задачи из P также входят в NP ?

> по другому быть не может

доказать пока никто не мог

/0

иначе говоря. он пишет что нашел алгоритм для задачи для которой есть полиномиальная проверка, полиномиальное решение.

то есть как максимум P \cap NP \neq \emptyset

хотя если доказано, что все задачи из P сводятся к решенной им задаче то тогда да :)

на правах зануды: M. Angela Weiss — это она, а не он ;)

> я в этом не специалист, но разве доказательство того, что ОДНА из задач из P также взодит в NP, доказывает то, что ВСЕ задачи из P также входят в NP ?

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

>>разве доказательство того, что ОДНА из задач из P также взодит в NP

Ты путаешь NP и NP-полноту. Задача выполнимости булевых формул NP-полная, а значит, если будет найден полиномиальный алгоритм, то автоматом P=NP.

Я верил!

>>то есть как максимум P \cap NP \neq \emptyset

Чудень, то что P полностью принадлежит NP, секретом является только для совершенно дремучих питекантропов.

Есть же класс NPC, для которого доказано, что NPC!=P. Взлом большинства симметричных криптоалгоритмов и некоторых асимметричных - именно NPC. Так что погодите с паникой. У криптологов, конечно, эта новость (если это правда) вызовет массу проблем с алгоритмами, стойкость которых находится «под вопросом», ну и все. Куда больше проблем оно вызовет у кванто-компьютерщиков, вплоть до полной их невостребованности.

Это, народ, я ни понел: спички, тушёнку и патроны уже пора запасать или ещё нет?

про 2012 не гон значит?

>>Куда больше проблем оно вызовет у кванто-компьютерщиков, вплоть до полной их невостребованности.

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

Да и вообще заманчиво моделировать квантовую систему не в кремнии, а напрямую в гильбертовом пространстве. Ещё Фейнман такое предлагал.

>>Есть же класс NPC, для которого доказано, что NPC!=P. Взлом большинства симметричных криптоалгоритмов и некоторых асимметричных - именно NPC.

NPC это же и есть NP-полные, чудо. Может, речь все-таки об NP-Hurd?

Мдя, не торт однако. В комментариях к проблеме тысячелетия сплошная некомпетентная школота, за очевидным исключением.

Не читал, но уверен что уета

Похоже на очередную попытку доказательства, не первую.

>В комментариях к проблеме тысячелетия сплошная некомпетентная школота, за очевидным исключением.
Вообще-то, ты на ЛОРе, да ещё и в толксах.

Ностальгирую по временам, когда и сам, когда учился, лил свои идеи на бумажку и сводил Exact cover к другим NP-complete задачам, на графах. В лучших традициях фермаистов-старшеклассников)

там по ссылкам в гугль групс автор доказательства обещает реализацию алгоритма. все с нетерпением ждут.

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

Думаю, что в данном случае результат немного предсказуем.

>А вроде ж P!=NP и по другому быть не может

В частных случаях. А в общем?

> Бразильский математик доказал что P=NP

Доказательство формализовано и прошло верификацию? Или это высер очередного шизофреника?

>>Доказательство формализовано и прошло верификацию? Или это высер очередного шизофреника?

Ты так говоришь, будто «или» у тебя исключающее.

я просто оставлю это (tue.nl) здесь

s/hurd/hard/

Маленький ликбез:

P ⊆ NP
NP-полные ⊆ NP
P ⊆ BPP (вероятностные) ⊆ BQP (квантовые)

(BQP ∩ NP-полные ≠ ∅) ⇔ (P = NP = NP-полные)

И да, почему в теме неадекваты?

>Это, народ, я ни понел: спички, тушёнку и патроны уже пора запасать или ещё нет?

уже поздно

Ссылка не открывается.

Там нормальное доказательство, с сведением NP-полной задачи к P?

C NP и P есть большая загвоздка.

Загвоздка вот в чём:

1) Если в доказательстве вместо вычислимости можно подставить относительную вычислимость, то оно неверно, так как для относительной вычислимости вопрос равенства NP и P может быть решён как в одну, так и в другую сторону (точно, могу накидать пинков и отсылок). Причём для случайного оракула вероятность того, что P ≠ NP равна единице (опять же, могу пнуть в нужном направлении, кому интересно).

2) Относительную вычислимость (вроде) можно подставить везде (тут я плохо разбираюсь, если честно, и буду благодарен, если пнут уже меня в нужном направлении).

>Ссылка не открывается.
Открывается. Там http://ompldr.org/vOHlxag и ссылка на http://groups.google.com/group/polynomial-algorithm-for-3-sat

Благодарю.

Да, обещает реализацию полиномиального решения задачи 3-выполнимости.

И, как следствие, задачи выполнимости для любых формул.

Будем ждать.

Эм.
Только у меня по ссылке:
The requested URL /~weiss/ was not found on this server.
?

Или этот университет уже уничтожили точечным ядерным ударом?

Хм, спасибо.

Хм. У меня открывалось из кэша.

Где найти статью. Какая степень полинома? И еще man NP hard

>>Доказательство формализовано и прошло верификацию? Или это высер очередного шизофреника?

Ты так говоришь, будто «или» у тебя исключающее.

Исключающее. После верификации оно перестает быть высером (кем бы ни был аффтар, уже не важно).

До верификации это вопрос веры в авторитет автора, после - вопрос веры в формальный вывод из аксиом. А доказательства обычно слишком сложны, чтобы просто так вот бросаться вычитывать их лично.

будем посмотреть месяца через два