P ≠ NP

[fregimus]

Чувак в «Хьюлит-Паккарде» работает, как бы не должен быть уж совсем уж фриком. Зовут Бинай Деолаликар (Vinay Deolalikar) — имя мне ни о чем не говорит. Утверждает, будто доказал P ≠ NP. Черновик (120 стр.) разослан коллегам, в журнал еще не отправлен.

Абстракт я читал, глядя как корчеватель на новые ворота — ничё не понял. Дальше, понятно, не совался. Скажите мне что-нибудь умное, а?

Доб. Небольшой начальный разбор в веб-журнале Ричарда Липтона.

Доб. http://kolokolca.livejournal.com/67206.html

Доб.Последняя запись Липтона вносит больше ясности:

I think there are several levels to the basic question “Is the proof correct?”:

1. Does Deolalikar’s proof, after only minor changes, give a proof that P ≠ NP?

2. Does Deolalikar’s proof, after major changes, give a proof that P ≠ NP?

3. Does the general proof strategy of Deolalikar (exploiting independence properties in random {k}-SAT or similar structures) have any hope at all of establishing non-trivial complexity separation results?

After all the collective efforts seen here and elsewhere, it now appears (though it is perhaps still not absolutely definitive) that the answer to #1 is “No”, [...] and the best answer to #2 we currently have is “Probably not, unless substantial new ideas are added.” But I think the question #3 is still not completely resolved, and still worth pursuing…

Comments

[kmmbvnr.livejournal.com]

http://kolokolca.livejournal.com/67206.html

[rwalk.livejournal.com]

Вроде бы уже и вердикт появился в одном из Ваших источников: http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p%E2%89%A0np-proof/. Я прочитал первые 3 главы препринта (непосредственно относящиеся к моей area of competence; в том, что касается собственно проблемы, я себя экспертом не могу считать) - и на мой взгляд изложение там весьма витиевато и запутанно (несмотря на появившиеся утверждения о том, что the paper is very well written), хотя возможно дело еще и в cultural gap между математикой и computer science (прошу прощения за смесь французского с нижегородским).

Встречный вопрос

[schegloff.livejournal.com]

А почему на эту тему такая шумиха? Разве NP-задачи (коммивояжер) не признаны уже полвека как алгоритмически неразрешимыми? Или я что-то путаю?

Re: Встречный вопрос

[palmas1.livejournal.com]

Я читал такое объяснение: современные криптосистемы основаны на NP-задачах, а если они на самом деле P, то существует быстрый алгоритм их взлома.

Возможно

[ccperm.livejournal.com]

Представляю тогда, какая бы шумиха возникла вокруг доказательства P=NP :)

Re: Встречный вопрос

[spamsink.livejournal.com]

Это странное объяснение. Ну, допустим, доказали бы, что NP сводимо к P с показателем степени, равным, чтобы не ходить далеко за примерами, порядку монстр-группы (≈ 8 · 10⁵³), ну и что?

Re: Встречный вопрос

[palmas1.livejournal.com]

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

Re: Встречный вопрос

[spamsink.livejournal.com]

Из любви к искусству. Интересно же, какие задачи можно в принципе решить "умнее", чем перебором, а какие - только перебором.

[fregimus.livejournal.com]

Спасибо.

[fregimus.livejournal.com]

Спасибо — с утра ее еще не было.

[praeinant.livejournal.com]

Абстракт я читал, глядя как корчеватель на новые ворота — ничё не понял. Дальше, понятно, не совался. Скажите мне что-нибудь...

Просто не думайте что он – гений, или что он – идиот...:)
...рас вопрос открытый (вы не вникли в вопрос...) скажите себе ''не знаю''...:)

А то есть некая возможность попасть и в такое положение:

Шахматами поигрываю лет сорок... И очень? странно когда новый партнер предчувствуя это все равно надеется поставить мат в четыре хода...
Конечно это метафора к другому... но что движет таким поведением... неуважение самого к себе?...

Re: Встречный вопрос

[jan-kiepura.livejournal.com]

Практика показывает, что полиномиальые алгоритмы редко бывают такой сложности. Вон, индусы придумали разложение на простые за полином от числа цифр. И степень то ли седьмая, то ли двенадцатая. Ну и в гипотезу Римана надо поверить, ну так верим же.

Re: Встречный вопрос

[cmike.livejournal.com]

Нет. Это гипотиза.

Re: Встречный вопрос

[fregimus.livejournal.com]

А почему на эту тему такая шумиха?
Кроме прочего, потому что за это мильон висит!

[abvgd.livejournal.com]

кстати сказать, проверить доказательство Деолаликара оказалось легче, чем доказать P != NP :)

[fregimus.livejournal.com]

А Вы разобрались в нем? Я не смог даже подступиться.

[cmike.livejournal.com]

Ну, введение (первая, что ли, глава) кажется неплохим первым шагом. ;)

Re: Встречный вопрос

[cmike.livejournal.com]

Это странное объяснение ещё и по другой причине. Принадлежность задачи к NP ничего не говорит о её криптостойкости, потому что NP-задача не обязана не иметь легко решаемых частных случаев. Например.

Re: Встречный вопрос

[janatem.livejournal.com]

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

[abvgd.livejournal.com]

нет, я и не пытался даже, забыл все это давно
просто раз ошибки так быстро нашлись, то и получается, что легче -- Деолаликар-то долго мучился )