[FOM] Polynomial Games
Harvey Friedman
friedman at math.ohio-state.edu
Wed Sep 30 02:13:02 EDT 2009
I wrote:
> 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.
There is a well defined notion of the "value" of the game G(P).
Because we are in a nice compact situation, the value of the game at
any stage of the play of the game, is continuous. From this we see
that there is a best possible first move for Alice. In particular,
there is a largest t such that Alice wins G(P,t).
What happens if we throw a computer package in to determine close
approximations to the value of G(P)? I would guess that when we are in
dimension 2k (i.e., there are k moves for each player), and the
polynomial is nontrivial, then the computer packages will blow up
badly, and give almost no information about the value of the game.
HOWEVER, note that the associated Tarski formula for, e.g., "the value
of the game is at least 1/2" is very simple and short:
(therexists x1)(forall y1)...(therexists xk)(forall yk)
(P(x1,y1,...,xk,yk) > 1/2).
You just have to fall in love with some polynomials P from [0,1]^2k
with rational coefficients to have some lovable hard problems with
presumably very small k.
If I am wrong about how hard these problems are, then we can move to
piecewise polynomials with rational coefficients
rationally semialgebraic functions
piecewise linear on the integers with integer coefficients
Presburger functions
Discontinuities should make things yet harder.
The last two stay within Presburger arithmetic.
Harveys
More information about the FOM
mailing list