[FOM] Polynomial Games
Harvey Friedman
friedman at math.ohio-state.edu
Tue Sep 29 17:50:35 EDT 2009
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
More information about the FOM
mailing list