Винэй Деолаликар

Биография

Индийский ученый-компьютерщик и исследователь; работает в компании 'HP Labs'.

Винэй Деолаликар родился в Нью-Дели, Индия (New Delhi, India). В Индийском Технологическом Институте (Indian Institute of Technology) в Бомбее (Bombay) он получил степень магистра по электроинженерии; позже, в Университете Южной Калифорнии (University of Southern California) ему была вручена степень доктора философии (примерный аналог русского кандидата наук).

6-го августа 2010-го Винэй разослал ведущим мировым исследователям манускрипт, в котором содержится его вариация решения одной из 'проблем тысячелетия' – проблемы равенства классов P и NP.

'Проблемы тысячелетия' – это 7 задач, находящиеся на стыке математики и ряда других наук. За решение каждой из них Математический Институт Клэя (Clay Mathematics Institute) обещал приз в 1 миллион долларов США. К текущему моменту лишь одна из семи задач была официально решена – русскому математику Григорию Перельману удалось доказать гипотезу Пуанкаре.

Равенство классов P и NP – одна из старейших задач информатики вообще и теории алгоритмов в частности. К классу NP относят ряд задач, решение которых 'тривиальным' методом потребует времени, являющего экспоненциальную степень от объема входных данных. Бытует мнение, что возможен некий алгоритм, позволяющий решить задачу за приемлемое, 'полиномиальное время'; к сожалению, доказать или опровергнуть этот факт до сего дня никому не удавалось. Практические изыскания подводят нас к тому, что классы P и NP, скорее всего, не равны между собой; если же кто-то сумеет доказать обратное, это будет гигантским прорывом в информатике. Множество проблем класса NP можно будет решить за адекватное время; кроме того, сильно пострадает криптография – большинство систем защиты информации как раз построены на том, что расшифровка ныне современных кодов по сложности относится к классу NP.

Впервые о манускрипте Винэя сообщил в своем блоге Грег Бэйкер (Greg Baker); новость быстро разлетелась по Иинтернет. На данный момент у доказательства есть как противники, так и сторонники; Скотт Аронсон (Scott Aaronson), к примеру, пообещал лично от себя добавить к обещанному институтом Клэя миллиону еще 200 тысяч долларов – в том случае, если решение окажется правильным. Мировым аналитикам еще только предстоит тщательно проанализировать труд Деолаликара – а в нем, надо отметить, 116 страниц – и сделать выводы о корректности доказательства.