P-position semilinearity conjecture for Exact Slow kk-Nim

From papers

Let \scNimn,=k1{\sc Nim}^1_{n,=k} be the impartial game on nonnegative integer vectors in which a move decreases exactly kk coordinates by one. A position from which the previous player can force a win is called a P-position. A set of integer vectors is semilinear if it can be expressed in Presburger arithmetic, equivalently as a finite union of solution sets of systems of linear inequalities and congruences. Semilinearity conjecture. For any nn and kk, the P-positions of \scNimn,=k1{\sc Nim}^1_{n,=k} form a semilinear set. The explicit characterization for \scNim6,=21{\sc Nim}^1_{6,=2} gives a polynomial-time decision procedure, motivating the conjecture for all values of nn and kk.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Nikolay Chikin, Vladimir Gurvich, Konstantin Knop, Mike Paterson and Michael Vyalyi, “More about Exact Slow k-Nim”, arXiv:2102.03528 (2021).

Solutions 0

No solutions have been posted yet.