за разумное время. Время счета теоретики считают разумным, если оно растет не быстрее чем некоторая степень от длины входа. К классу NP принадлежат задачи, правильность предъявленного решения которых можно быстро проверить. Однако для поиска решения задачи из класса NP может потребоваться неприемлемо большое время. К этому классу относится множество практически важных задач, например, задача коммивояжера - как объехать набор городов по кратчайшему маршруту. Она точно решается только алгоритмами, мало отличающимися по эффективности от прямого перебора всех маршрутов. В семидесятых годах прошлого века было показано, что в классе NP есть так называемые NP-полные задачи, к которым сводится решение любой задачи из этого класса. Одна из них это задача коммивояжера.
С тех пор математики пытаются либо найти алгоритм, решающий какую-нибудь из NP-полных задач за степенное время, то есть доказать что P=NP, либо доказать, что таких алгоритмов не существует. А на этой гипотезе зиждется все шифрование данных по алгоритмам с открытым ключом. И только гипотетические квантовые компьютеры способны решать задачи из NP за степенное время.
Но и доказать, что P не равно NP, уже много лет не удается. Не удается и доказать, что это доказать невозможно, а значит, утверждение о неравенстве можно принять в качестве еще одной аксиомы в основаниях математики. Ученые перешли в осаду и время от времени обнаруживают, что те или иные известные методы доказательств не могут решить эту проблему. Свой вклад в этот процесс вносит и статья лауреатов. В ней показано, что целый класс так называемых 'натуральных' доказательств тоже не может решить проблему. А это значит, что надо искать какие-то другие пути. Впервые результаты этой статьи были доложены на симпозиуме по теории вычислений еще тринадцать лет тому назад, и этого времени оказалось достаточно, чтобы коллеги по достоинству оценили значение работы. ГА
Как известно, новые вирусы и трояны появляются в Сети с завидной регулярностью и чем дальше, тем гуще. Борцы с этим злом тоже не отстают. 'Лаборатория Касперского' перешла с неупорядоченного - как бог на душу положит - на годичный цикл выпуска новых версий своего антивирусного пакета для конечных пользователей. Год назад появилась 'шестерка', а теперь состоялся анонс седьмого поколения KAV и KIS [Kaspersky AntiVirus и Kaspersky Internet Security. Второй содержит файрволл и прочие интернет-компоненты.], которые выйдут 07.07.2007 (интересно, не будет ли на дистрибутиве магических пентаграмм или охраняющих рун?).
Первый возникающий по этому поводу вопрос: 'Зачем?' - чего такого не хватало в шестой редакции, чтобы оправдать умножение сущностей?
На самом деле даже разработчики признают, что ничего революционного не появилось, это просто эволюция в соответствии с изменившимися требованиями рынка и характером угроз. Конечно, ЛК не могла проигнорировать эпоху Windows Vista - интерфейс программы теперь выполнен в соответствующем стиле. Однако одними 'рюшечками' адаптация под новую ОС не ограничивается, есть поддержка и 64-разрядной Vista, и механизма контроля прав пользователя UAC, а все сетевые и файловые драйверы подписаны в сертификационной лаборатории Microsoft. Помимо 'солидности' (при инсталляции Windows не высказывает опасений в том, что неизвестный разработчик может украсть серебряные ложки или еще чего похуже сделать), это еще и гарантия
