10
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I'd guess that roots of the polynomial in question would be the possibility-trees of "winning continuations", i.e. paths that leads to mate by force. What kind of polynomial that takes trees as input, I don't know! $\endgroup$ – Bobson Dugnutt Feb 9 '16 at 16:58
  • 1
    $\begingroup$ In the modern rules of professional chess the number of possible games is finite (see FIDE.com for an exhaustive list of all the rules if you want.) Estimated as between $10^{120}$ and $10^{200}$. $\endgroup$ – DanielWainfleet Feb 12 '16 at 21:21
  • $\begingroup$ @user254665 Indeed and this finiteness property is what makes it possible to encode the game into polynomials over finite fields. I am curious as how the theory of finite fields can be used in such combinatorial setting as games. $\endgroup$ – TheNicanova Feb 12 '16 at 21:26
  • 1
    $\begingroup$ Scott Aaronson has a stackexchange account. I just sent him an email since I figure he might be well equipped to answer a question about what he meant on his blog. $\endgroup$ – Mark S. Feb 13 '16 at 0:07
  • $\begingroup$ @MarkS. Thanks a lot! $\endgroup$ – TheNicanova Feb 13 '16 at 0:25
9
+50
$\begingroup$

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 kth 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!

$\endgroup$
  • $\begingroup$ Is it possible to reasonably estimate the order of magnitude of the numbers involved for a game like chess? (i.e. size of the field, degree of the polynomial, $n$ the number of variables of the polynomial). $\endgroup$ – user1892304 Jan 2 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.