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

This paper considers the computational complexity of computing winning
strategies in games where two
players, I and II, take turns choosing positive integers,
*x _{1},x_{2},x_{3},...,x_{n}* and the win
condition is a polynomial equation in

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

**
**

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

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