Return to list of publications of J.P. Jones.

**J.P. Jones, Computational complexity of winning strategies in
polynomial two player games (Russian), Theory of Computational
Complexity vol. 5, D.Yu. Grigoriev ed., Zapiski Nauchnikh Seminar Leningrad
Branch Steklov Math. Institute vol. 192 (1991) 69-73.
**

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, n is the length of the game. The two players, I and II,
alternately choose nonnegative integers, *
x _{1},x_{2},x_{3},...,x_{n}*. The player
having the last move wishes to make the polynomial

An old theorem of von Neumann and Zermelo states that every finite
length, positional, win-lose game with perfect information is determined.
That is, there exists a winning strategy for one player or the other.
In a 1982 paper (#16) the author proved that for *n = 6* there need be
no recursive (computable) winning strategy for either player. In the present
paper it is proved that for *n = 4* there need be no polynomial
time computable winning strategy for either player.

**
**

A theorem about *NP* completeness of decision problems for such two
player games is also proved. The problem of deciding whether player I has
a winning strategy in a game of length *n = 2* is proved to be *NP*
complete.

Return to list of publications of J.P. Jones.