В рамках направления «Математическая теория информации и управления, многокомпонентные случайные системы» в лаборатории проводятся исследования по теме: проблемы эффективного описания объектов, процессов, алгоритмов на основе теорий модельной полноты, интуиционистской и дескриптивной теорий множеств, теории моделей, нестандартного анализа и стохастических игр. Эти исследования ведут д.ф.-м.н. П.В. Голубцов, к.ф.-м.н. К.Ю. Горбунов, д.ф.-м.н. В.Г. Кановей, д.ф.-м.н. В.А. Любецкий, к.ф.-м.н. А.В. Селиверстов.

(0) Основные результаты по этой теме состоят в следующем. Доказано, что центральные алгебры и многие полупервичные кольца имеют модельные компаньоны. Сформулирована и доказана связь между модельной полнотой локализаций колец и самого кольца. Описан широкий класс формул, для которых из их доказуемости в классической теории множеств следует интуиционистская доказуемость тех же или близких к ним формул. Последнее означает, что для доказанной функциональной зависимости, описанной одной из этих формул, можно построить терм, а в случае дискретных переменных – алгоритм, которые описывают/вычисляют эту зависимость.

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

Впервые эффективно построено возрастающее конфинальное семейство борелевских отношений эквивалентности и порождающих их идеалов.

Решена проблема эффективной канонизации борелевских отношений эквивалентности, ограниченных на борелевские множества, для которых отношение Витали сохраняет основные свойства, например, свойство невозможности эффективного перечисления классов эквивалентности вещественными числами. Доказано, что помимо двух тривиальных типов (полная неэквивалентность и полная эквивалентность) имеется лишь один нетривиальный тип: само отношение Витали. Проведена классификация упорядоченных структур Хаусдорфа с точки зрения существования специальных подструктур (щелей, пределов и т.д.).

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

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

Доказано, что даже весь теоретико-множественный универсум допускает эффективно определенное нестандартное расширение, причем насыщенное в любой мощности (решение старой проблемы).

Доказана полиномиальная верхняя оценка на число эффективных стратегий (монотонных правил выбора), хоть одна из которых позволяет найти загаданную строку t из нулей и единиц с существенным перевесом правильных угадываний её битов над неправильными, если известно, что t принадлежит заданному не слишком большому подмножеству строк известной длины. Доказано, что существование n-клики в n-дольном графе с двумя вершинами в каждой доле эквивалентно непустоте многогранника, стороны которого вычисляются за полиномиальное от n время. Предложен алгоритм поиска n-клики в указанном многодольном графе с помощью алгоритма линейного программирования. Размерность соответствующего многогранника позволяет оценивать сверху число таких клик. С другой стороны, показано, что естественные задачи, связанные с поиском в n-дольном графе с двумя вершинами в каждой доле, n-клики с дополнительными свойствами, являются алгоритмически сложными в предположении, что классы NP и coNP различны.

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

Подробнее см. список публикаций в математических журналах.