Главная : Дневники : Ruby NoName Podcast :

Ruby NoName Podcast S04E10

Новости

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
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)
M. Vardi, Complexity of Relational Query Languages
N. Immerman, Relational Queries Computable in Polynomial Time ( и дают th. Immerman-Vardi, что FO(LFP) = P)
Wiki, где собраны основные данные о проверке и paper
По всей видимости первое или одно из первых упоминаний в интернете о paper
Первый комментарий проф. Liption
Ссылки на остальные есть в wiki, вот еще важный комментарий,
где Liption публикует письмо Immerman, что Deolalikar безосновательно использует только mondaic fixed points и
указывает, что он полагается на это свойство в своем доказательстве, но указывает, что тогда он получает не все P. Тем
самым получается, что Deolalikar неправильно применяет теорему Immermana-Vardi. Ошибка найдена!
Прочее: упоминал «кирпич»: Т. Кормен, Ч. Лейзерсон, Р. Ривест, «Алгоритмы: построение и анализ»


Текущее

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


Контакты

Наш твиттер
Email для предложенией

СКАЧАТЬ ВЫПУСК   01:17:41, 44.5 Мб
добавлен 24.05.12 22:26

жизнь продолжается
Radio Grinch Выпуск 077
СКАЧАТЬ ВЫПУСК   48:10, 33.1 Мб
добавлен 01.02.15 08:59
Снова в школу
Шопинг по-американски
Radio Grinch Выпуск 074
СКАЧАТЬ ВЫПУСК   01:06:12, 45.5 Мб
добавлен 09.07.14 01:37
Дело Кинчева и не только...
Ленинград vs Москва глазами молодого писателя [nobr]80-х[/nobr]
Ленинградское время Выпуск 23
СКАЧАТЬ ВЫПУСК   23:23, 16.1 Мб
добавлен 10.09.13 14:30
Архив выпусков рубрики

На главную
О проекте
Программы
Контакты

Полная версия
Вход