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

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