?

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

cmike
Aug. 12th, 2010 03:00 pm (UTC)
Re: Встречный вопрос
Это странное объяснение ещё и по другой причине. Принадлежность задачи к NP ничего не говорит о её криптостойкости, потому что NP-задача не обязана не иметь легко решаемых частных случаев. Например.