Исследования поддержаны грантом РНФ

Учеными Университета Лобачевского под руководством ведущего научного сотрудника ИИТММ ННГУ, профессора Института математики Уорикского университета (Великобритания) Лозина Вадима Владиславовича реализуется научный проект «Алгоритмические, сложностные и структурные вопросы теории графов и дискретной оптимизации».

На практике очень часто возникают важные задачи, в которых надо выбрать оптимальный вариант из ограниченного, но, возможно, очень большого множества. Такие задачи называются задачами дискретной, или комбинаторной, оптимизации. Теоретически они могли бы быть решены путем перебора всех вариантов и выбора из них лучшего, но на практике такой перебор часто не осуществим, так как потребовал бы колоссального времени даже на современных высокопроизводительных компьютерах. Поэтому для таких задач ученые ищут непереборные и, по возможности, быстрые, алгоритмы.

Новые алгоритмы могут быть успешно использованы в исследовании и развитии сложнейших сетевых структур и найти своё применение в телекоммуникационной и IT сферах, логистике, транспортной системе и многих других сферах жизнедеятельности человека.

К задачам дискретной оптимизации относятся, например, задачи на графах. Графом в математике называют объект, состоящий из точек (называемых узлами или вершинами графа) и соединяющих некоторые из этих точек линий (называемых дугами или ребрами). Например, с помощью графа можно изобразить сеть дорог между городами. Тогда города будут представляться узлами графа, а дороги между ними ? дугами.

Графом можно изобразить компьютерную локальную сеть или даже всю всемирную сеть Интернет. Здесь узлами будут компьютеры, а соединены дугой будут только те узлы, для которых соединены соответствующие им компьютеры. Чтобы доставить сообщение от одного компьютера другому, требуется определить наикратчайший путь между ними.

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

Удобным и достаточно универсальным языком, на котором удается описать задачи дискретной оптимизации (включая задачи на графах) является целочисленное линейное программирование.

За более чем полвека исследований для части задач дискретной оптимизации были найдены быстрые алгоритмы (т.е. алгоритмы, время работы которых ограничено полиномом от длины входной информации). К полиномиально разрешимым задачам относятся, например, задачи о кратчайшем пути в графе, о максимальном потоке, о наибольшем паросочетании и многие др.

Для другой большой части задач быстрых алгоритмов найдено не было. Все усовершенствования алгоритмов для таких трудноразрешимых, «неподдающихся» задач мало чем отличаются от прямого перебора, несмотря на усилия тысяч специалистов. К неподдающимся относятся, например, задачи о клике, о минимальном покрытии, о максимальном независимом множестве и многие др.

Тем не менее, остается открытым вопрос: «а существуют ли в принципе быстрые алгоритмы для «неподдающихся» задач или такие эффективные алгоритмы пока еще не найдены?» Большинство специалистов склоняется к мнению, что таковых алгоритмов для большинства неподдающихся задач не существует, поэтому их никто никогда не сможет найти. Если будет доказана известнейшая гипотеза «P ≠ NP», то это будет означать, что это действительно так.

Проблема «P = NP?» была сформулирована в 1971 г. С.Куком, но до сих пор никто не доказал P = NP или P ≠ NP. Это одна из самых главных открытых проблем в теоретической информатике. Математический институт Клэя в 2000 г. назвал ее первой среди семи нерешенных важнейших «Задач тысячелетия». 

Проблема построения полиномиальных алгоритмов и проблема изучения границы эффективной разрешимости порождают ряд сложных математических задач, над которыми трудится коллектив исследователей ННГУ. 

К этим задача относятся: исследование строения пересечения целочисленной решетки с полиэдром, в частности, описание граней выпуклой оболочки этого пересечения; исследование граничных классов графов; увеличивающих графов; построение эффективных алгоритмов и соответствующих нижних оценок для решения ряда задач (например, о независимом множестве, покрытии, упаковки) на классах графов; построение эффективных алгоритмов решения задач дискретной оптимизации (например, минимизации квазивыпуклых функций на целочисленной решетке) и др.