Jones, J. P. Computational complexity of winning strategies in two player polynomial games. (Russian. English summary) Zbl 0757.90097 Zap. Nauchn. Semin. Leningr. Otd. Mat. Inst. Steklova 192, 69-73 (1991). Summary: 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 is the length of the game. The two players alternately choose nonnegative integers \(X_ 1,X_ 2,\dots,X_ l\). The player having the last move whishes to make the polynomial \(P(X_ 1,X_ 2,\dots,X_ l)=0\). The other player wishes to make \(P(X_ 1,X_ 2,\dots,X_ l)\neq 0\).An old theorem of von Neumann and Zermelo states that any finite, positional, win-lose game with perfect information is determined. That is, there exists a winning strategy for one player or the other. The author proved [Int. J. Game Theory 11, 63-70 (1982; Zbl 0498.90090)] that for \(l=6\) (games of length 6) there need be no recursive (computable) winning strategy for either player. In the present paper, it is proved that for \(l=4\), there need be no polynomial time computable winning strategy for either player.A theorem about NP-completeness of problems in two player polynomial games is also given. The problem of deciding whether player I has a winning strategy in games of length \(l=2\) is NP-complete. A proof is sketched. Cited in 1 Review MSC: 91A46 Combinatorial games 90C60 Abstract computational complexity for mathematical programming problems Keywords:polynomial time computable winning strategy; NP-completeness Citations:Zbl 0498.90090 PDFBibTeX XMLCite \textit{J. P. Jones}, Zap. Nauchn. Semin. Leningr. Otd. Mat. Inst. Steklova 192, 69--73 (1991; Zbl 0757.90097) Full Text: EuDML