`

СПЕЦИАЛЬНЫЕ
ПАРТНЕРЫ
ПРОЕКТА

Архив номеров

Как изменилось финансирование ИТ-направления в вашей организации?

Best CIO

Определение наиболее профессиональных ИТ-управленцев, лидеров и экспертов в своих отраслях

Человек года

Кто внес наибольший вклад в развитие украинского ИТ-рынка.

Продукт года

Награды «Продукт года» еженедельника «Компьютерное обозрение» за наиболее выдающиеся ИТ-товары

 

Андрей Дегелер

Проблема P≠NP решена?

Сегодня обнаружил в открытом доступе новую попытку решения одной из важнейших задач теории алгоритмов — вопроса о равенстве классов сложности P и NP. Она, кстати, является одной из «проблем тысячелетия», за решение которых исследователь получает от Математического института Клэя 1 млн долл. Ещё одной такой проблемой была, например, гипотеза Пуанкаре, доказанная Григорием Перельманом.

Описание проблемы можно прочесть в Википедии (англ., рус.), а скачать доказательство — по этой ссылке.

Исследование Виная Деолаликара (Vinay Deolalikar) из лаборатории HP в Пало Альто датировано 6 августа. Можно с уверенностью утверждать, что в ближайшие несколько недель научная общественность будет усиленно искать ошибки в доказательстве.

Но то, что спустя два дня их вроде как не найдено, — уже повод для оптимизма. Например, два года назад, когда Xian-Jin Li опубликовал свою версию доказательства ещё одной «проблемы тысячеления» — гипотезы Римана, — первое указание на ошибку появилось уже на следующий день.

+77
голосов

Напечатать Отправить другу

Читайте также

Лиш бы не было как сдесь http://xkcd.ru/664/ :)

 
 
IDC
Реклама

  •  Home  •  Рынок  •  ИТ-директор  •  CloudComputing  •  Hard  •  Soft  •  Сети  •  Безопасность  •  Наука  •  IoT