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.

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, n is the length of the game. The two players, I and II, alternately choose nonnegative integers, x1,x2,x3,...,xn. The player having the last move wishes to make the polynomial P(x1,x2,x3,...,xn) = 0. The other player wishes to make the polynomial P(x1,x2,x3,...,xn) nonzero.

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.

I picks x1,
I picks x2,
I picks x3,
I picks x4,

II wins iff x3(x3x4 - x2 - 1)(x1 + x4 - x3) = 0.

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.