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

J.P. Jones and Aviezri S. Fraenkel, Complexities of winning strategies in diophantine games., Jour. of Complexity vol. 11 (1995), 435-455. MR 97c:68066.

Abstract

A classical theorem of von Neumann 1928 and Zermelo 1912 (see also von Neumann and Morgenstern 1953) states that every finite length, two-person, win-lose game with perfect information is determined. That is, there exists a winning strategy for one player or the other. The length of a game is the number of moves. Finite length means a finite number of moves. Win-lose means no draws are possible. Perfect information means no randomness is involved, also that each player informs the other of his choices.

Even though such a game is determined, there may be no computable winning strategy for either player (see paper 16). The present [1995] paper considers the computational complexity of computing winning strategies in diophantine games. A diophantine game is a game in which two players, I and II, take turns choosing natural numbers x1,x2,x3,...,xn. The win condition is a polynomial equation in x1,x2,x3,...,xn. Player I chooses the odd subscripted variables and player II chooses the even subscripted variables.

A diophantine game of length n = 4 is constructed with the property that neither player I nor II has a polynomial time computable winning strategy:

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

Here player II can win but player II has no polynomial time computable winning strategy for selecting x2. Hence neither player has a polynomial time computable winning strategy.

Another theorem in the paper is the construction of a diophantine game G6 of length 6 with the property that one of the players has a polynomial time computable winning strategy in G6 iff P = NP. Also constructed is a game N6 of length 6 such that player II has a polynomial time computable winning strategy in N6 iff co-NP = NP.

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