Курс состоит из нескольких тем, относящихся к теории игр и алгоритмической сложности решения игр. Предварительного знания основных определений и фактов в теории игр не требуется: они будут, хотя бы кратко, рассказаны.

В начале будут рассказаны классические результаты о решении конечных игр и приведены примеры PSPACE-полных игр. Далее будет обсуждено (не-)существование выигрышных стратегий для бесконечных игр и дано доказательство существования особо простых стратегий (позиционные стратегии, стратегии с конечной памятью) для игр из нескольких интересных классов: игры чётности, циклические игры, простые стохастические игры. Существование таких стратегий имеет важные следствия для алгоритмической сложности решения таких игр, помещая эту задачу в пересечение классов NP и coNP. Основной темой курса является изложение недавно придуманных квазиполиномиальных алгоритмов для решения игр чётности. Для циклических игр будут рассказаны вероятностные субэкспоненциальные алгоритмы (лучше пока не получается).

Для понимания курса желательно знакомство с основными понятиями теории сложности вычислений: машины Тьюринга, основные сложностные классы, понятие сводимости. Текст содержит лишь короткие напоминания по этим вопросам. Для более подробного ознакомления с теорией сложности рекомендуются стандартные учебники, например, Сипсера или Ароры и Барака. Желательно также знакомство с базовыми алгоритмами (топологическая сортировка, построение кратчайших путей и т.п.).