|
Zapiski Nauchnykh Seminarov 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.
Citation:
J. P. Jones, “Computational complexity of winning strategies in two player polynomial games”, Computational complexity theory. Part 5, Zap. Nauchn. Sem. LOMI, 192, Nauka, Leningrad, 1991, 69–73; J. Math. Sci., 70:4 (1994), 1887–1889
Linking options:
https://www.mathnet.ru/eng/znsl4947 https://www.mathnet.ru/eng/znsl/v192/p69
|
Statistics & downloads: |
Abstract page: | 137 | Full-text PDF : | 43 |
|