[FOM] Polynomial Games

[Harvey Friedman]

Let P:[0,1]^2k into [a,b] be a polynomial with rational coefficients.

We let G(P,t) be the following two person game.

Alice and Bob alternately play k moves, where each move is an element  
of [0,1].

Let x,y in [0,1]^k, where Alice's moves form x, and bob's moves form y.

Alice wins if P(x,y) > t. Bob wins if P(x,y) <= t.

It would seem extremely difficult to determine who wins G(P,t), even  
for small k.

For instance, use k = 2.

Let P(x,y,z,w) = c_1 xy + c_2 xz + c_3 xw + c_4 yz + c_5 yw + c_6 zw

where we can fiddle with the c's. E.g.,

P1(x,y,z,w) = xy - xz - xw + yz - yw + zw.

23(x,y,z,w) = xy - 2xz - xw + 2yz + yw - zw.

Let rng(P1) = [a,b], rng(P2) = [c,d].

Take t = a + (b-a)/8, a + 2(b-a)/8, ..., a + 7(b-a)/8 for P1.

Take t = a + (d-c)/8, a + 2(d-c)/8, ..., a + 7(d-c)/8 for P2.

This gives us 14 games G(P1,t), G(P2,t). Hence 14 questions: does  
Alice win?

Note that all of these questions are naturally first order in the  
field of reals, which is decidable.

If this isn't hard enough, raise k and provide more c's.

Harvey Friedman