El truco utilizado en la prueba de la complejidad doblemente exponencial de la aritmética Presburger

Publiqué esto en MathUnderflow pero no obtuve respuestas, así que pensé en probarlo aquí,

Estoy leyendo el viejo artículo de Rabin y Fischer [publicará un enlace cuando sea posible] donde, entre otras cosas, se prueba la doble complejidad exponencial de la aritmética de Presburger.

La prueba se basa en la existencia de una fórmula afirma informalmente " " con . Aunque la construcción de esta fórmula no se da en el documento, ¡fue una sorpresa para mí teniendo en cuenta que es presumiblemente altamente no trivial, dado ese límite y el hecho de que solo tenemos adición a nuestra disposición! $I_{n}(x)$ $x < 2^{2^{kx+1}}$ $|I_{n}| \in O(n)$

Más tarde supe que la construcción de esta fórmula se basa en un "truco", previamente descubierto por Fischer, y de forma independiente por Volker Strassen, ¡pero no he logrado localizar un documento que describe este truco en detalle!

Entonces, si alguien sabe sobre el papel del que estoy hablando y puede señalarme en su dirección o incluso describirme el truco ...

Esta publicación del blog de Lipton contiene un enlace al documento y menciona [y proporciona un esbozo aproximado, lamentablemente insuficiente para mí], dicho truco, por cierto.

¹ Sé que esta es una descripción vaga. Sin embargo, una descripción suficientemente detallada sería demasiado larga para una publicación de SX, así que solo espero que alguien que ya conozca el documento en cuestión, y que por lo tanto pueda conformarse con ese breve boceto, se encuentre con esto y pueda ayudarme. .

complexity-theory reference-request logic mojado
fuente

¿Cuál es la relación entre

? ¿O debería ser

n

$n$

k

$k$

2^{2^{n x + 1}}

$2^{2^{nx+1}}$

Shaull

Puede descargar el documento de Fisher & Rabin aquí .

Martin Berger

La construcción se da en el documento: Teorema 8 en las páginas 14-15 (la declaración real es el Corolario 9 en la página 16).

Yuval Filmus

Respuestas:

El comentario de Martin (y el seguimiento de Yuval) da la referencia que explica la construcción con cierto detalle.

$2^{2^{c\cdot n}}$ $M_n(x,y,z)$

M_{n} (x, y, z) \Leftrightarrow x \times y = z \land x < 2^{2^{n}}

$M_n(x,y,z) \Leftrightarrow x\times y=z\ \wedge x< 2^{2^n}$

$M_n$ $n$

$M_{n+1}(x,y,z)$

M_{n} (x_{1}, y_{1}, z_{1}) \land M_{n} (x_{2}, y_{2}, z_{2}) \land M_{n} (x_{3}, y_{3}, z_{3})

$M_{n}(x_1,y_1,z_1)\wedge M_{n}(x_2,y_2,z_2)\wedge M_{n}(x_3,y_3,z_3)$

\forall u v w, (u = x_{1} \land v = y_{1} \land w = z_{1}) \lor (u = x_{2} \land v = y_{2} \land w = z_{2}) \lor (u = x_{3} \land v = y_{3} \land w = z_{3}) \Rightarrow M_{n} (u, v, w)

$\forall u v w,(u=x_1\wedge v=y_1\wedge w=z_1)\vee(u=x_2\wedge v=y_2\wedge w=z_2)\vee(u=x_3\wedge v=y_3\wedge w=z_3)\Rightarrow M_n(u,v,w)$

$n$

Hay un par de otros trucos involucrados, pero este es el principal. Los aspectos internos de la recursión son importantes, por supuesto, pero la similitud con el truco de Karatsuba es realmente sorprendente.

cody
fuente

Algunos podrían reconocer el truco cuantificador de la prueba de

P S P A C E = N P S P A C E

$PSPACE=NPSPACE$ .

Ariel