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

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

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

Источник: www.youtube.com

Комментарии: