Юрий Лифшиц | Блог (yury_lifshits) wrote,
Юрий Лифшиц | Блог
yury_lifshits

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

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

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


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

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic
  • 14 comments