Complexities of Winning Strategies in Diophantine Games

This paper considers the computational complexity of computing winning strategies in diophantine games, where two players take turns choosing natural numbers x₁, x₂, x₃, . . . , x_n and the win condition is a polynomial equation in the variables x₁, x₂, . . . , x_n. A diophantine game G₄ of length 4 is constructed with the propertythat neither player has a polynomial time computable winning strategy. Also a diophantine game G₆ of length 6 is constructed with the property that one of the players has a polynomial time computable winning strategy in G₆ iff P = NP. Finally a diophantine game N_b of length 6 is constructed such that one of the players has a polynomial time computable winning strategy in it iff co-NP = NP.