О трудности решения беспристрастных игр

В докладе будет рассказано об одном сюжете из теории алгоритмических игр — анализе сложности решения беспристрастных игр. Хорошо известный алгоритм построения ядра ориентированного графа решает такую игру за время, линейное от размера графа позиций игры. Оказывается, существуют игры, для которых этот алгоритм оптимален с точностью до полиномиального ускорения. Будет дана точная формулировка этого результата и кратко описаны основные идеи доказательства. Доклад основан на результатах, полученных М. Вялым и В