Mi pregunta se basa en uno de Scott Aaronson blog , que establece que un Dios-como podría ser convencido de los aldeanos, para cualquier grado de confianza, que ella ha resuelto de ajedrez por responder a algunas preguntas acerca de los ceros de algunos polinomios sobre campos finitos. Sé que tiene que ver con PSPACE = IP, pero me pregunto cómo sería de codificar este tipo de juegos (como el ajedrez) en los polinomios de más de campo finito?
Respuesta
¿Demasiados anuncios?
La respuesta a esta pregunta no es nada más ni menos que la prueba de $IP=PSPACE$ --- ver por ejemplo aquí o aquí. La prueba funciona tomando una arbitraria TQBF fórmula $\phi$ (es decir, una fórmula proposicional con cuantificadores universal y existencial, tales como la fórmula que codifica "Blanco tiene las de ganar en el ajedrez") y, a continuación, la construcción de un multivariante polinomio $p:\mathbb{F}^n\rightarrow\mathbb{F}$ sobre un gran campo finito $\mathbb{F}$, de tal manera que
$$\sum_{x_1,\ldots,x_n\in \{0,1\}^n} p(x_1,\ldots,x_n) \ne 0$$
si y sólo si $\phi$ es cierto. (Con alguna complicación adicional causado por la necesidad de "grado de reducción" para manejar los cuantificadores universal y existencial---pero no vamos a entrar en eso.)
Usted puede entonces tener un armario y verificador de participar en una interacción, donde en el kth ronda, el armario de las reclamaciones que, si se restringen los primeros a $k-1$ variables $x_1,\ldots,x_{k-1}$ $p$ a acordadas previamente los valores de $r_1,...,r_{k-1}$, y la suma de los últimos $n-k$ variables$x_{k+1},\ldots,x_n$, $p$ simplifica a algunos polinomio univariado $q_k(x_k)$. A continuación, el comprobador retos de esta afirmación mediante la selección de un valor aleatorio uniformemente $r_k$$x_k$, y el juego continúa. En cada ronda, el verificador puede verificar si la $q_k$ que se dice que es consistente con lo que se afirma en la siguiente ronda. Luego, al final, el verificador puede evaluar a $p(r_1,\ldots,r_n)$ por sí mismo, y comprobar si es igual a $q_n(r_n)$. Utilizando el Teorema Fundamental del Álgebra, se puede demostrar que, si la demanda original no era cierto (es decir, $\phi$ es falso e $p$ sumas a cero), entonces no importa lo que el armario no, con alta probabilidad de al menos uno de los verificador comprueba que descubrir esto. Así obtenemos un sonido protocolo---y desde el TQBF problema es $PSPACE$-completo, que implica la $PSPACE\subseteq IP$, y, por tanto,$IP=PSPACE$.
Si quieres, también puedes ver toda la interacción entre el armario y el comprobador de un jugador, perfecto-información del juego: en este caso, una nueva versión de la original juego de ajedrez. Pero el nuevo juego tiene la maravillosa propiedad de que, para desempeñar de manera óptima, la única cosa que el verificador nunca necesita hacer es elegir al azar $\mathbb{F}$-elementos $r_1,\ldots,r_n$! El demostrador, por otro lado, las necesidades a resolver un $PSPACE$-un problema en el fin de calcular los polinomios univariados $q_1,\ldots,q_n$ que hará que el armario de "ganar" la interacción (es decir, provocar el comprobador de admitir que, sí, $\phi$ es verdad, después de todo).
De nuevo, para más detalles, lea alguna de las pruebas de $IP=PSPACE$ disponible en la web!
