?

Log in

No account? Create an account

Previous Entry | Next Entry

P ≠ NP

Чувак в «Хьюлит-Паккарде» работает, как бы не должен быть уж совсем уж фриком. Зовут Бинай Деолаликар (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…

Tags:

Comments

( 20 comments — Leave a comment )
fregimus
Aug. 12th, 2010 05:53 am (UTC)
Спасибо.
rwalk
Aug. 12th, 2010 03:23 am (UTC)
Вроде бы уже и вердикт появился в одном из Ваших источников: 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 (прошу прощения за смесь французского с нижегородским).
fregimus
Aug. 12th, 2010 06:03 am (UTC)
Спасибо — с утра ее еще не было.
schegloff
Aug. 12th, 2010 03:33 am (UTC)
Встречный вопрос
А почему на эту тему такая шумиха? Разве NP-задачи (коммивояжер) не признаны уже полвека как алгоритмически неразрешимыми? Или я что-то путаю?
palmas1
Aug. 12th, 2010 04:23 am (UTC)
Re: Встречный вопрос
Я читал такое объяснение: современные криптосистемы основаны на NP-задачах, а если они на самом деле P, то существует быстрый алгоритм их взлома.
ccperm
Aug. 12th, 2010 04:29 am (UTC)
Возможно
Представляю тогда, какая бы шумиха возникла вокруг доказательства P=NP :)

spamsink
Aug. 12th, 2010 04:35 am (UTC)
Re: Встречный вопрос
Это странное объяснение. Ну, допустим, доказали бы, что NP сводимо к P с показателем степени, равным, чтобы не ходить далеко за примерами, порядку монстр-группы (≈ 8 · 1053), ну и что?
palmas1
Aug. 12th, 2010 04:47 am (UTC)
Re: Встречный вопрос
Наверное, это всё же экзотика. Иначе чего ради вообще выделять эти группы задач?
spamsink
Aug. 12th, 2010 04:56 am (UTC)
Re: Встречный вопрос
Из любви к искусству. Интересно же, какие задачи можно в принципе решить "умнее", чем перебором, а какие - только перебором.
jan_kiepura
Aug. 12th, 2010 06:26 am (UTC)
Re: Встречный вопрос
Практика показывает, что полиномиальые алгоритмы редко бывают такой сложности. Вон, индусы придумали разложение на простые за полином от числа цифр. И степень то ли седьмая, то ли двенадцатая. Ну и в гипотезу Римана надо поверить, ну так верим же.
cmike
Aug. 12th, 2010 03:00 pm (UTC)
Re: Встречный вопрос
Это странное объяснение ещё и по другой причине. Принадлежность задачи к NP ничего не говорит о её криптостойкости, потому что NP-задача не обязана не иметь легко решаемых частных случаев. Например.
cmike
Aug. 12th, 2010 06:43 am (UTC)
Re: Встречный вопрос
Нет. Это гипотиза.
fregimus
Aug. 12th, 2010 06:58 am (UTC)
Re: Встречный вопрос
А почему на эту тему такая шумиха?
Кроме прочего, потому что за это мильон висит!
janatem
Aug. 13th, 2010 08:11 am (UTC)
Re: Встречный вопрос
NP-задачи, как тривиально следует из определения, алгоритмически разрешимы.
praeinant
Aug. 12th, 2010 06:10 am (UTC)
Абстракт я читал, глядя как корчеватель на новые ворота — ничё не понял. Дальше, понятно, не совался. Скажите мне что-нибудь...

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

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

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

abvgd
Aug. 12th, 2010 01:07 pm (UTC)
кстати сказать, проверить доказательство Деолаликара оказалось легче, чем доказать P != NP :)
fregimus
Aug. 12th, 2010 01:25 pm (UTC)
А Вы разобрались в нем? Я не смог даже подступиться.
cmike
Aug. 12th, 2010 02:51 pm (UTC)
Ну, введение (первая, что ли, глава) кажется неплохим первым шагом. ;)
abvgd
Aug. 13th, 2010 02:51 pm (UTC)
нет, я и не пытался даже, забыл все это давно
просто раз ошибки так быстро нашлись, то и получается, что легче -- Деолаликар-то долго мучился )
( 20 comments — Leave a comment )