RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1991 Volume 192, Pages 69–73 (Mi znsl4947)

Computational complexity of winning strategies in two player polynomial games

J. P. Jones


Abstract: Two player games of the following type are considered. A game is defined by a polynomial $P$, with integer coefficients. The number of variables in the polynomial is the length of the game. The two players alternately choose nonnegative integers $X_1,X_2,\dots,X_l$. The player having the last move wishes to make the polynomial $P(X_1,X_2,\dots,X_l)=0$. The other player wishes to make $P(X_1,X_2,\dots,X_l)\ne0$.
An old theorem of von Neumann and Zermelo states that any finite, positional, win-lose game with perfect information is determined. That is, there exists a winning strategy for one player or the other. In [4] the author proved that for $l=6$ (games of length 6) there need be no recursive (computable) winning strategy for eigher player. In the present paper, it is proved that for $l=4$, there need be no polynomial time computable winning strategy for either player.
A theorem about $NP$ completeness of problems in two player polynomial games is also given. The problem of deciding whether player I has a winning strategy in games of length $l=2$ is $NP$-complete. A proof is sketched.

UDC: 518.5


 English version:
Journal of Mathematical Sciences, 1994, 70:4, 1887–1889

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024