Юрий Лифшиц / Блог

Поскольку сильную реакцию вызвала предыдущая статья, выкладываю еще один draft.

Юрий Лифшиц, Дмитрий Павлов
Fast Exponential Deterministic Algrithm for Mean Payoff Games

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


А так, вчера был на концерте АукцЫона. Отличный концерт.
От всей души поздравляю vma_tm с прошедшим днем рожденья!