А. Давыдов

Алгоритм Д.Ю. Григорьева для решения тропических линейных систем

Решение тропической линейной системы --- задача, которая лежит в пересечении NP и coNP.

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

Алгоритм интересен тем, что несмотря на то, что на практике он работает крайне быстро, полиномиальных оценок на время выполнения для него --- нет.