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.
**

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
*x _{1},x_{2},x_{3},...,x_{n}*. The win
condition is a polynomial equation in

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:

**
**

Here player II can win but player II has no polynomial time computable
winning strategy for selecting *x _{2}*. Hence neither player
has a polynomial time computable winning strategy.

Another theorem in the paper is the construction of a diophantine game
*G _{6}* of length 6 with the property that one of the players
has a polynomial time computable winning strategy in

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