Исследователь HP претендует на то, чтобы взломать сложность Compsci Convertrum

Хотя Hewlett-Packard барабаны из падение его генерального директора Марка Херда уходит, компания может искупаться во славе хотя бы одного потенциально позитивного достижения: исследователь HP предложил то, что он говорит, решение одной из самых сложных проблем в информатике.

Главный научный сотрудник HP Labs Винай Деолиликар опубликовал то, что, по его утверждению, является решением того, что широко известно как проблема P против NP.

Так трудно понять, что Институт математики глины пообещал наградить человека, который его решает. 1 миллион долларов. Это одна из семи проблем, которые все вместе называются «Задачами тысячелетия», институт предложил эту щедрость. Одна из семи гипотез Пуанкаре была официально разрешена в 2006 году.

Пока неясно, получит ли Деолаликар наличные деньги, так как Клей не сказал, что считает, что проблема решена.

Эта проблема, «одна из выдающиеся проблемы в информатике, «включает в себя» определение того, существуют ли вопросы, чей ответ можно быстро проверить, но которые требуют невероятно долгого времени для решения любой прямой процедуры », - поясняет страница Института. В этой задаче P обозначает полиномиальное время, а NP означает недетерминированное полиномиальное время.

«Я рад объявить доказательство того, что P не равен NP», - заявил Deolalikar по электронной почте группе профессоров-математиков, который затем был опубликован в воскресенье Грегом Бейкером, доцентом из Университета Британской Колумбии Симона Фрейзера.

В двух словах это может означать, что некоторые проблемы могут быть решены только путем поиска грубой силы, если решения можно найти в все.

«Доказательство требовало сложения принципов из нескольких областей в математике. Основные усилия по построению этого доказательства заключались в выявлении цепочки концептуальных связей между различными полями и их просмотре через общую линзу», - писал Деоликарик.

Естественно, те, кто хорошо разбирается в этой проблеме, стесняются заявить, что Deolalikar решил проблему, учитывая количество проверок, которые необходимо будет сделать. И хотя они похвалили Deolalikar за его тщательный подход, который отличается от более случайных догадок, которые обычно представлены, никто окончательно не заявил, что он взломал проблему.

«Кажется, это вызывает некоторые мыслимые новые идеи, особенно связь между статистической физикой и логической характеристикой NP первого порядка, - писал Скотт Ааронсон, доцент электротехники и информатики Массачусетского технологического института, в непринужденной записи в блоге.

«Я не знаю, что подумать прямо сейчас, но я, безусловно, надеюсь, - писал Дик Липтон, профессор информатики в Технологическом институте Джорджии.

Joab Jackson охватывает корпоративное программное обеспечение и общие технологии, новости о которых для Служба новостей IDG. Следуйте за Joab в Twitter на @Joab_Jackson. Адрес электронной почты Joab - [email protected]