Кафедра математической логики и теории алгоритмов

Механико-математического факультета МГУ


Компьютерные технологии. Сложность вычислений и проблема перебора

Естественно, что построенный в математической логике аппарат анализа интеллектуальной, в частности, математической деятельности оказался востребованным, когда электроника «доросла» до математики в деле создания «математических машин», называемых компьютерами. В «эру компьютеров» и под влиянием вычислительных наук в математике были получены важные результаты, в том числе — нашими сотрудниками и выпускниками. На вводных лекциях по системному программированию часто вспоминают теорему Успенского, которая утверждает алгоритмическую невозможность распознать по программе какого-либо нетривиального свойства вычисляемой ею функции. С 1988 г. до последних дней жизни в 1993 г. нашей кафедрой заведовал академик Владимир Андреевич Мельников, участник создания самого знаменитого советского компьютера БЭСМ-6 и многих других отечественных компьютеров, включая супер-ЭВМ. (В последней работе принимал участие и А. Л. Семенов.)

Самой важной и самой загадочной проблемой современной математики и ее приложений сегодня называют проблему перебора — выяснения того, можно ли некоторые естественно возникающие в практике и теории задачи решать существенно быстрее, чем просто перебором вариантов. Явная формулировка этой проблемы и соответствующие математические утверждения были найдены параллельно американским математиком Куком и студентом нашей кафедры, учеником А.Н. Колмогорова Леонидом Анатольевичем Левиным. Сегодня Л. А. Левин — лауреат премии Кнута, профессор Бостонского университета.

Среди наиболее впечатляющих попыток частичного решения этой проблемы — результат Александра Александровича Разборова, который рассмотрел алгоритмы некоторого естественного вида и решил проблему для них. А. А. Разборов получил свой результат, будучи студентом нашей кафедры. Сегодня он — член-корреспондент РАН, сотрудник Математического института им. В.А. Стеклова РАН и Чикагского университета, лауреат премий Неванлинны и Гёделя.

В настоящее время широкий спектр исследований по теории сложности ведется и выпускниками нашей кафедры, учениками В. А. Успенского, профессором Николаем Константиновичем Верещагиным и Александром Шенем, при участии их учеников. В них также принимал участие Ан. А. Мучник. В этом и последующих разделах мы приводим несколько примеров нерешенных задач в данной области, связанных с результатами, полученными этими математиками. Среди важных объектов изучения — так называемые односторонние функции. Так называются функции, которые легко (быстро) вычислить, но трудно обратить (чтобы найти некоторый прообраз данного объекта, требуется много времени). Односторонние функции применяются во всех современных протоколах защиты информации, а также при построении генераторов псевдослучайных чисел. Сложность вычислений связана с колмогоровской сложностью (о ней речь пойдет дальше) и с коммуникационной сложностью. И та, и другая используются в сложности вычисления как средство доказательства нижних оценок времени, необходимого для решения конкретных задач. Другим важным инструментом являются коды с исправлением ошибок. Вот пример нерешенной задачи в коммуникационной сложности: задача о различении близких и далеких слов.