Proving that one has solved chess by exhibiting the zeroes of polynomials over finite fields?

Question

My question is based on one of Scott Aaronson blog post which states that a God-like being could convinced the villagers, to any degree of confidence, that she has solved chess by answering a few questions about the zeroes of some polynomials over finite fields. I know it has to do with PSPACE = IP, but I am wondering how one would encode such games (as chess) into polynomials over finite field?

Answer 1

The answer to this question is nothing more or less than the proof of $IP=PSPACE$ --- see for example here or here. The proof works by taking an arbitrary TQBF formula $\phi$ (i.e., a propositional formula with universal and existential quantifiers, such as the formula that encodes "White has the win in chess"), and then constructing a multivariate polynomial $p:\mathbb{F}^n\rightarrow\mathbb{F}$ over a large finite field $\mathbb{F}$, such that

$$\sum_{x_1,\ldots,x_n\in \{0,1\}^n} p(x_1,\ldots,x_n) \ne 0$$

if and only if $\phi$ is true. (With some additional complication caused by the need for "degree reduction" to handle the universal and existential quantifiers---but let's not go into that.)

You can then have a prover and verifier engage in an interaction, where in the k^th round, the prover claims that, if you restrict the first $k-1$ variables $x_1,\ldots,x_{k-1}$ of $p$ to previously-agreed values $r_1,...,r_{k-1}$, and sum over the last $n-k$ variables $x_{k+1},\ldots,x_n$, then $p$ simplifies to some specific univariate polynomial $q_k(x_k)$. The verifier then challenges this claim by picking a uniformly random value $r_k$ for $x_k$, and the game continues. At each round, the verifier can check whether the $q_k$ that was claimed is consistent with what's claimed in the next round. Then, at the very end, the verifier can just evaluate $p(r_1,\ldots,r_n)$ for itself, and check whether it equals $q_n(r_n)$. By using the Fundamental Theorem of Algebra, you can prove that, if the original claim wasn't true (i.e., $\phi$ is false and $p$ sums to zero), then no matter what the prover does, with high probability at least one of the verifier's checks will uncover this. So we get a sound protocol---and since the TQBF problem is $PSPACE$-complete, it implies $PSPACE\subseteq IP$, and hence $IP=PSPACE$.

If you want, you can also see the entire interaction between prover and verifier as a two-player, perfect-information game: in this case, a transformed version of the original game of chess. But the new game has the amazing property that, in order to play optimally, the only thing the verifier ever needs to do is pick random $\mathbb{F}$-elements $r_1,\ldots,r_n$! The prover, on the other hand, needs to solve a $PSPACE$-complete problem in order to calculate the univariate polynomials $q_1,\ldots,q_n$ that will cause the prover to "win" the interaction (i.e., cause the verifier to admit that, yes, $\phi$ is true after all).

Again, for more details, read any of the proofs of $IP=PSPACE$ available on the web!