Игры вычитания и полулинейные множества (Михаил Вялый)

Математический семинар факультета компьютерных наук ВШЭ Игры вычитания — широкий класс беспристрастных игр. Основная тема лекции — алгоритмическая сложность решения игр вычитания. По сути речь идет о сложности вычисления функций, заданных рекуррентными соотношениями особого вида. Известно, что для некоторых игр эта задача трудна, а для некоторых проста. Во втором случае и появляются полулинейные множества — многомерный аналог арифметических прогрессий. Граница между «трудными» и «простыми» играми пока неясна. Будут предложены некоторые гипотезы, уточняющие эту границу. Выступает профессор Михаил Вялый, ведущий научный сотрудник международной лаборатории теоретической информатики ФКН ВШЭ. 17 ноября 2023 Математический семинар ФКН: ФКН: ​​ Подписывайтесь на нас: 📍 ​​/ 📍 📍