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

J.P. Jones, Computational complexity of computing winning strategies in polynomial games., Nanjing Daxue Xuebao Shuxue Bannian Kan 8 (1991), No. 1, 1-5.

Abstract

This paper considers the computational complexity of computing winning strategies in games where two players, I and II, take turns choosing positive integers, x1,x2,x3,...,xn and 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. The games thus have bounded length, n moves.

A 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 (x1 + x4 - x3)(x3x4 - x2) = 0.

Player II can win in the above game but player II has no polynomial time computable winning strategy for selecting x2. Hence neither player has a polynomial time computable winning strategy.

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