Алгоритмы и оценки в тропической алгебре

Алгоритмы и оценки в тропической алгебре

Speaker:

Дмитрий Юрьевич Григорьев

Date:

Tuesday, August 25, 2015 - 18:00

Abstract:

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

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

Классическая теорема Гильберта о нулях (в двойственной форме) сводит разрешимость системы полиномиальных уравнений к разрешимости системы линейных уравнений с матрицей Маколея. Совместно с В.Подольским мы доказываем тропическую версию двойственной теоремы Гильберта о нулях и приводим для неё точные оценки (в классическом случае точные оценки для неё были получены ГаллигоХайнцемКолларом). Отметим, что прямой аналог теоремы Гильберта о нулях в тропическом мире неверен, поэтому рассматривается двойственная форма.

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