30 ноября 2012 года

Алгоритмы решения линейных тропических систем

Алексей Павлович Давыдов (Академический университет РАН, С.-Петербург)

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