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

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

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

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