Журнал «Компьютерра» № 21 от 05 июня 2007 года

Наибольший интерес американские химики проявляют к материаловедению, нанотехнологиям, биохимии, аналитической химии и химии атмосферы. Меньше всего интереса у янки вызывают ядерная, теоретическая и вычислительная химии (оно и понятно – теоретическая химия, конечно, занятие не всегда прибыльное). ЕГ

Viva teoria!

В этом году Приз Геделя будет вручен российскому математику Александру Разборову и американцу Стивену Рудичу (Steven Rudich) за их совместную статью «Натуральные доказательства» (Natural Proof), опубликованную в 1997 году.

Приз Геделя за выдающиеся статьи в области Theoretical Com-puter Science учрежден и спонсируется Европейской ассоциацией теоретических компьютерных наук (EATCS) и Теоретической группой Международной ассоциации компьютерных вычислений ACM-SIGACT. Одна из самых престижных для компьютерщиков премий вручается ежегодно начиная с 1993 года и включает небольшое денежное вознаграждение в пять тысяч долларов. Российский ученый удостаивается этого приза впервые.

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

С тех пор математики пытаются либо найти алгоритм, решающий какую-нибудь из NP-полных задач за степенное время, то есть доказать что P=NP, либо доказать, что таких алгоритмов не существует. А на этой гипотезе зиждется все шифрование данных по алгоритмам с открытым ключом. И только гипотетические квантовые компьютеры способны решать задачи из NP за степенное время.

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

Седьмой номер KAV и KIS: ты ловить умеешь крыс?

Как известно, новые вирусы и трояны появляются в Сети с завидной регулярностью и чем дальше, тем гуще. Борцы с этим злом тоже не отстают. «Лаборатория Касперского» перешла с неупорядоченного – как бог на душу положит – на годичный цикл выпуска новых версий своего антивирусного пакета для конечных пользователей. Год назад появилась «шестерка», а теперь состоялся анонс седьмого поколения KAV и KIS [Kaspersky AntiVirus и Kaspersky Internet Security. Второй содержит файрволл и прочие интернет-компоненты.], которые выйдут 07.07.2007 (интересно, не будет ли на дистрибутиве магических пентаграмм или охраняющих рун?).

Первый возникающий по этому поводу вопрос: «Зачем?» – чего такого не хватало в шестой редакции, чтобы оправдать умножение сущностей?

На самом деле даже разработчики признают, что ничего революционного не появилось, это просто эволюция в соответствии с изменившимися требованиями рынка и характером угроз. Конечно, ЛК не могла проигнорировать эпоху Windows Vista – интерфейс программы теперь выполнен в соответствующем стиле. Однако одними «рюшечками» адаптация под новую ОС не ограничивается, есть поддержка и 64-разрядной Vista, и механизма контроля прав пользователя UAC, а все сетевые и файловые драйверы подписаны в сертификационной лаборатории Microsoft. Помимо «солидности» (при инсталляции Windows не высказывает опасений в том, что неизвестный разработчик может украсть серебряные ложки или еще чего похуже сделать), это еще и гарантия определенного уровня стабильности – сертификация сопровождается тщательным тестированием на совместимость.