– Анатолий Васильевич, что даёт решение этой задачи? В чём её важность?

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

– Разве не очевидно, что все задачи класса P принадлежат классу NP?

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

– Что вам удалось сделать?

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

– Как появилась идея заняться задачей тысячелетия?

– Работая в ЧПИ, на кафедре прикладной математики, я занимался решением прикладных задач для нефтегазодобывающей промышленности Западной Сибири. Там необходимо было при заданном размещении скважин определять точки сбора нефти. Удалось построить эффективный алгоритм. По результатам работы защитил кандидатскую диссертацию. Затем стал решать более абстрактные задачи, уровень обобщения повышался. Постепенно я пришёл к мысли о возможности эффективно решить и NP-трудную задачу.

– Как долго работали над решением?

– Более тридцати лет. В течение этого времени написаны статьи, программы для ЭВМ, которые вошли в комплекс компьютерных программ, использовавшихся для проектирования инфраструктуры Западной Сибири. Тогда по результатам работы вуз был награжден премией Миннефтепрома.

– Где-то докладывали о результатах работы над задачей тысячелетия?

– Да, в Институте математики и механики УрО РАН, в Уфимском государственном авиационном техническом университете (УГАТУ). Кроме того, летом и осенью прошлого года сделаны доклады на международных научных форумах в Словакии и Черногории. Результаты направлены в международный научный журнал «Дискретная математика». Выступал на юбилейной конференции факультета ВМИ ЮУрГУ. В мае этого года планирую выступить с докладом в Москве, в Институте проблем управления РАН.

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

– В чём преимущества этого решения?

– В лаконичности и простоте. Статья с результатами уместилась на двенадцати страницах.

– Будут ли результаты исследования использоваться в учебном процессе?

– Думаю, часть его ляжет в основу исследовательских работ бакалавров и магистров, а возможно – и диссертаций.

– Каковы дальнейшие планы?

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