August 13th, 2010

ДР Цертуса 2011

Status report

Введение в суть происходящего в трёх словах: //www.ugcs.caltech.edu/~stansife/pnp.html
Страница, где сообщество общими усилиями анализирует доказательство: //p-is-not-np.tk

Результаты экспертного сообщества по анализу (P ≠ NP)-доказательству Деолаликара на данный момент по мнению Ричарда Липтона написал Терри Тао:
“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” (as seen for instance in the issues documented in the wiki), 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 (though not at the hectic internet speed of the last few days).”
ДР Цертуса 2011

(no subject)

Я тут пишу о том, как наши корабли бороздят просторы, обо всяких P и NP, о светлом ядерном будущем!
А оказывается, всё это не нужно, потому что у нас уже есть всё. Наше всё. И у этого светила есть имя!
СМИ сообщают, что благодаря Ему распускаются цветы!

“Он — светоч мира, оплот свободы!
Грехи отпустит и примет роды!
Слепой прозреет, ослепнет зрячий:
Владимир Путин не х.. собачий!

Он самый мудрый и самый добрый,
Он — солнцеликий, богоподобный!
Не страшны голод, война, цунами —
Навеки Путин пребудет с нами!”
— ВИА Беломорс — “Владимир Путин”
  • Current Music
    Группа “Несчастный случай” — Путин и Христос.
ДР Цертуса 2011

(no subject)

А как делать архив ЖЖ с комментами из под Ubuntu? У меня ljArchive что-то с первого раза не запустился, да и вообще старый он какой-то, может часть фич не поддерживает..
ДР Цертуса 2011

(no subject)

Я попробовал Perl 6, конкретно то, чем они заменили там регэкспы — так называемый Perl Rules. Это разумно устроенный однородный конгломерат из регэкспов, EBNF основанного не контекстно-свободных грамматиках, а на возможно-контекстно-зависимом Parsing Expression Grammar-формализме, и собственно кода сопровождения парсинга. При помощи этой штуки можно за 30 минут (I mean it literally) написать “взрослый” парсер для формата средней сложности, выдающий пользователю разумные сообщения об грамматических ошибках в тексте с предположением, что пользователь хотел написать. Это бомба. Перл всегда был языком, в которым удобно работать с текстом. Perl 6 продолжает эту традицию, так больше нигде не сделаешь. Офигительно.