Новости * Libskypekit and Skypekit – C and Ruby interface for Skype * Gem для работы с Google spreadsheet * Поддержка PostgreSQL datatypes в Rails 4 * Ruby 2.0 roadmap * The Bastards Book of Ruby * Continuos deployment for ruby gems * Ruboto 0.6.0 * Mechanize 2.5 * Гем для асинхронной отсылки почты из devise - devise-async * Глава из книги Ruby Under a Microscope * Последняя попытка попасть на devConf

Обсуждение NP-полнота * Для ознакомления с базовыми определениями и теоремами рекомендуется к прочтению книга: М. Гэри, Д. Джонсон, «Вычислительные машины и труднорешаемые задачи». * Random_k-SAT * [VV1986] L. G. Valiant, V. V. Vazirani, NP is as easy as detecting unique solutions (показано, что поиск solutions to instances having a unique solutions, are as hard as SAT, under randomized reduction) * [Var1982] M. Vardi, Complexity of Relational Query Languages * [Imm1986] N. Immerman, Relational Queries Computable in Polynomial Time ([Imm1982] и [Var1982] дают th. Immerman-Vardi, что FO(LFP) = P) * Wiki, где собраны основные данные о проверке и paper * По всей видимости первое или одно из первых упоминаний в интернете о paper * Первый комментарий проф. Liption * Ссылки на остальные есть в wiki, вот еще важный комментарий, где Liption публикует письмо Immerman, что Deolalikar безосновательно использует только mondaic fixed points и указывает, что он полагается на это свойство в своем доказательстве, но указывает, что тогда он получает не все P. Тем самым получается, что Deolalikar неправильно применяет теорему Immermana-Vardi. Ошибка найдена! * Прочее: упоминал «кирпич»: Т. Кормен, Ч. Лейзерсон, Р. Ривест, «Алгоритмы: построение и анализ»

Текущее * Наш конкурс закончился, результаты подводятся * Иван Евтухович ушел работать в Express42.