[FOM] Re: My latest opinion

[Timothy Y. Chow]

A word of advice to those who don't know Doron Zeilberger: His opinions
should only be taken x% seriously, where x is a variable that you have to
learn how to assess.  Part of the fun of reading his opinions is figuring
out what parts he's dead serious about and what parts are tongue in cheek
and thrown in just for effect.  My guess is that he's absolutely serious
that (for example) P = NP is a more important problem than the Riemann
Hypothesis.  His evaluation of specific remarks of Hardy should be taken
less seriously, because he was probably less concerned with 100% accurate
exegesis than with making a particular point.  If you latch on to the
wrong part of his article, then the joke's on you.

Anatoly Vorobey wrote:
> It's not because chess is finite, unlike number theory
> or real analysis or what have you; it's because the rules of chess are
> incidental. A chess problem does not give rise to nontrivial mathematics
> because it is governed by incidental (and historically accidental) rules
> which are very unlikely to connect in any meaningful way to the existing
> body of mathematics, much less to enrich it or to contribute to it.

This might be true of short directmate problems.  In general, though, the
ad hoc nature of chess rules does not automatically prevent chess from
enriching the body of mathematics.  It is true that the definition of
chess (or of generalized chess, played on an nxn board) is highly
unnatural and hence chess is probably never going to take a place
side-by-side with a Hilbert space or a finite field as an object of
obvious intrinsic mathematical interest.  However, chess can *connect*
to and *inspire* and *enrich* mathematics.

A simple example is Fraenkel and Lichtenstein's proof that generalized
chess is EXPTIME-complete.  Although it is unlikely, it is not impossible
that having this concrete and rather unusual instance of an EXPTIME-
complete problem will be useful in computational complexity.

Here's a question I posed a couple of years ago that is still open.  What
is the computational complexity of the following problem?  Given two
generalized chess positions A and B, determine whether or not position
B can be reached from position A through a series of legal chess moves,
where we ignore the 50-move rule (actually the 50-move rule does not
result in an *automatic* draw, so strictly speaking this proviso is not
necessary, but I state it anyway to avoid confusion).  The problem is
easily seen to be in PSPACE, and Hans Bodlaender showed that it is NP-hard
by reduction from Hamiltonian circuit for grid graphs.

  http://www.google.com/groups?selm=98t90a%24lej%241%40samos.cs.uu.nl

It's not clear that it's in NP, though, because the obvious certificate
---the sequence of legal moves connecting A and B---could conceivably be
exponentially long.  Consideration of special cases of this problem seems
to lead naturally into some interesting questions in algorithmic graph
theory.

Tim