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