Prueba de asociatividad

Prueba de asociatividad : comprobación de la asociatividad de una operación binaria . El procedimiento de verificación ingenua, que consiste en la enumeración de todos los tripletes posibles de argumentos de la operación, lleva tiempo, donde es el tamaño del conjunto sobre el que se define la operación. Las primeras pruebas de asociatividad no proporcionaron mejoras asintóticas sobre el algoritmo ingenuo, pero mejoraron el tiempo de ejecución en algunos casos especiales. Por ejemplo, Robert Tarjan descubrió en 1972 que la prueba de Light, propuesta en 1949, permite verificar si la operación binaria en estudio es reversible (da un cuasigrupo $O(n^{3})$ $norte$ $O(n^{2}\log n)$ ). La primera prueba probabilística que mejora el tiempo de ejecución de a fue propuesta en 1996 por Sridhar Rajagopalan y Leonard Shulman . En 2015, se propuso un algoritmo cuántico que verifica la asociatividad de una operación en el tiempo , lo cual es una mejora con respecto a la búsqueda de Grover , que se ejecuta en [1] . $O(n^{3})$ ${\ estilo de texto O (n ^ {2} \ registro \ delta ^ {-1})}$ ${\ estilo de texto O (n ^ {10/7})}$ ${\ estilo de texto O (n ^ {3/2})}$

Planteamiento del problema

Dada una tabla de tamaño que describe una operación cerrada sobre un conjunto de tamaño , es decir, la operación viene dada por su tabla de Cayley , y junto con esta operación forma un magma . Hay que comprobar que para cualquiera se cumple (es decir, la operación es asociativa ). Cualquier algoritmo determinista que resuelva este problema requerirá no menos tiempo, ya que cada celda de la tabla de Cayley debe leerse al menos una vez. La enumeración iterativa de todos los triples , comprobando que la igualdad se cumple para cada triple, lleva tiempo [2] . $n\veces n$ $\cdot :G\veces G\mapsto G$ $GRAMO$ $norte$ $\cdot$ $GRAMO$ ${\ estilo de visualización a, b, c \ en G}$ $a\cdot (b\cdot c)=(a\cdot b)\cdot c$ $O(n^{2})$ $a B C$ $O(n^{3})$

Motivación

La comprobación de la asociatividad es uno de los problemas naturales que surgen al trabajar con tablas Cayley de varias operaciones [3] . En particular, dicha verificación se implementa en los sistemas de álgebra computacional GAP [4] y Maple [5] . En el caso más general, hay operaciones para las cuales todos menos uno de los triples son asociativos; un ejemplo de tal operación en elementos es la operación tal que , y para todos los demás elementos . Su única terna no asociativa es , porque [6] . Debido a la existencia de tales operaciones, uno puede tener la impresión de que la verificación de asociatividad requerirá procesar todos los triples posibles y, por lo tanto, es imposible una mejora asintótica en el tiempo de ejecución del algoritmo [7] . Por la misma razón, un algoritmo probabilístico ingenuo que comprueba la asociatividad de triples seleccionados aleatoriamente requerirá comprobaciones para garantizar una probabilidad de error suficientemente baja [8] . Sin embargo, el algoritmo propuesto por Rajagopalan y Shulman muestra que esta estimación se puede mejorar y sirve como un claro ejemplo de cómo los algoritmos probabilísticos pueden hacer frente a problemas que parecen difíciles para los algoritmos deterministas: a partir de 2020, los algoritmos deterministas resuelven un problema dado en subcúbico. tiempo , desconocido [9] . $n\geq 3$ $\cdot$ $1\cdot 2=2$ $a\cdot b=3$ ${\ estilo de visualización 1,1,2}$ $1\cdot (1\cdot 2)=1\cdot 2=2\neq 3=3\cdot 2=(1\cdot 1)\cdot 2$ $O(n^{3})$

Prueba de luz

En 1961, Alfred Clifford y Gordon Preston publicaron en el libro Algebraic Semigroup Theory una prueba de asociatividad informada a uno de los autores por el Dr. Light en 1949. El algoritmo consiste en considerar para cada operación y . Por definición, una operación es asociativa si y solo si (las tablas de operaciones de Cayley son las mismas) para todo [10] . Light notó que si , es decir, y tiene un grupo electrógeno , entonces es suficiente verificar solo [11] [12] . $g\in G$ $x\star _{g}y=x\cdot (g\cdot y)$ $x\circ _{g}y=(x\cdot g)\cdot y$ $\cdot$ ${\ estilo de visualización \ estrella _ {g} = \ circ _ {g}}$ $g\in G$ $G=\langle S\rangle$ $GRAMO$ $S$ ${\ estilo de visualización g \ en S}$

Si en las definiciones anteriores y , entonces . ${\ estilo de visualización \ estrella _ {a} = \ circ _ {a}}$ ${\ estilo de visualización \ estrella _ {b} = \ circ _ {b}}$ ${\ estilo de visualización \ estrella _ {a \ cdot b} = \ circ _ {a \ cdot b}}$

Prueba

Que sea para todos . entonces _ ■ $(x\cdot a)\cdot y=x\cdot (a\cdot y)$ $(x\cdot b)\cdot y=x\cdot (b\cdot y)$ ${\ estilo de visualización x, y \ en G}$ $x\cdot ((a\cdot b)\cdot y)=x\cdot (a\cdot (b\cdot y))=(x\cdot a)\cdot (b\cdot y)=(( x\cdot a)\cdot b)\cdot y=(x\cdot (a\cdot b))\cdot y$

En el peor de los casos (por ejemplo, para el máximo funcionamiento ), el grupo electrógeno de magma más pequeño puede estar formado por elementos, por lo que habrá que realizar la prueba de todos los elementos , lo que llevará tiempo. En 1972 , Robert Tarjan notó que la prueba de Light puede ser efectiva para probar si una operación determinada define un grupo [2] . Esto se debe al hecho de que para algunos tipos especiales de operaciones, incluidas las operaciones que satisfacen el axioma de grupo de la presencia de un elemento inverso , siempre es posible seleccionar un grupo electrógeno de pequeño tamaño [12] . ${\ estilo de texto n}$ ${\ estilo de texto G}$ ${\ estilo de texto O (n ^ {3})}$

Deje que cualquier ecuación de la forma tenga una solución única (es decir , un cuasigrupo ). Entonces en él es posible singularizar un grupo electrógeno de tamaño máximo . $GRAMO$ ${\ estilo de visualización a = b \ c punto x}$ $X$ $GRAMO$ $GRAMO$ $S$ $\lpiso \log _{2}n\rpiso +1$

Prueba

Sea un subconjunto tal que y . Entonces, debido al hecho de que es un cuasigrupo, , ya que todos los elementos de la forma son diferentes y no están contenidos en . Por lo tanto, la adición secuencial a los elementos de la vista no se puede realizar más de una vez. ■ $T\subconjunto G$ $GRAMO$ $G\neq \langle T\rangle$ $b\in G\setminus \langle T\rangle$ $(G,\cdot)$ $\vert \langle T\cup \{b\}\rangle \vert \geq 2\vert \langle T\rangle \vert$ $t\cdot b$ $t\in \langle T\rangle$ $\langle T\rangle$ $T\neq \varnada$ $b\in G\setminus \langle T\rangle$ ${\ estilo de visualización \ log _ {2} \ vert G \ vert}$

Por definición, es un cuasigrupo si y solo si su cuadro de Cayley es un cuadrado latino , lo cual puede verificarse en el tiempo . La aplicación del procedimiento descrito anteriormente a un cuasigrupo permite, a su vez , comprobar de forma determinista si , es un grupo , para [13] . $GRAMO$ ${\ estilo de texto O (n ^ {2})}$ $GRAMO$ $O(n^{2}\log n)$

Prueba de Rajagopalan-Schulman

La primera prueba subcúbica fue el algoritmo tipo Monte Carlo propuesto en 1996 [14] Sridhar Rajagopalan de la Universidad de Princeton y Leonard Shulman del Instituto de Tecnología de Georgia . El procedimiento propuesto por ellos requiere tiempo, donde es la máxima probabilidad de error admisible [3] [7] . $O(n^{2}\log\delta^{-1})$ $\delta$

Algoritmo

El algoritmo utiliza un álgebra grupoide , un espacio lineal ( álgebra ) sobre un campo de dimensión de dos elementos , cuyos vectores base corresponden a todos los diferentes elementos del magma . Los vectores de tal espacio tienen la forma ${\ estilo de visualización \ mathbb {Z} _ {2} [G]}$ $\mathbb{Z} _{2}$ $norte$ $v_{g_{1}},\puntos,v_{g_{n}}$ $g_{1},\puntos,g_{n}$

{\textstyle A=a_{g_{1}}v_{g_{1}}+a_{g_{2}}v_{g_{2}}+\puntos +a_{g_{n}}v_{g_{n }}=\sum \limits _{g\in G}a_{g}v_{g}}

, dónde

a_{g}\en \mathbb {Z} _{2}.

Tienen la operación suma

{\textstyle A+B=\sum \limits _{g\in G}(a_{g}\oplus b_{g})v_{g))

, donde denota adición y en

\oplus

{\ Displaystyle a_ {g}}

{\ Displaystyle b_ {g}}

{\ estilo de visualización \ mathbb {Z} _ {2},}

así como la operación del producto

{\textstyle A\cdot B=\sum \limits _{x,y\in G}a_{x}b_{y}v_{x\cdot y}=\sum \limits _{g\in G}(\ bigoplus \limits _{x\cdot y=g}a_{x}b_{y})v_{g}}

, donde denota el producto y en

{\ Displaystyle a_ {x} b_ {y}}

{\ Displaystyle a_ {x}}

{\ Displaystyle b_ {y}}

{\ estilo de visualización \ mathbb {Z} _ {2}.}

El producto de vectores en tal álgebra se vuelve más intuitivo si consideramos que para cualquier par de vectores base se define como , y el producto de cualquier otro par de vectores se obtiene "abriendo los paréntesis" y reorganizando los términos. Por ejemplo, para el producto tiene la forma ${\displaystyle v_{x}\cdot v_{y}=v_{x\cdot y))$ $G=\{p,q,r\}$

A\cdot B=(a_{p}v_{p}+a_{q}v_{q}+a_{r}v_{r})\cdot (b_{p}v_{p}+b_{ q}v_{q}+b_{r}v_{r})=a_{p}b_{p}(v_{p}\cdot v_{p})+a_{p}b_{q}(v_{p }\cdot v_{q})+\dots +a_{r}b_{r}(v_{r}\cdot v_{r}),

y la sustitución da como resultado una expresión correspondiente a la definición general [8] . Para el álgebra así definida, se cumple el siguiente lema [15] : ${\displaystyle v_{x}\cdot v_{y}=v_{x\cdot y))$

La operación inicial del magma es asociativa si y solo si para cualquier . Si la operación no es asociativa, entonces la probabilidad de que se satisfaga la igualdad especificada para un triple elegido aleatoriamente de manera uniforme no excede . $A\cdot (B\cdot C)=(A\cdot B)\cdot C$ ${\ estilo de visualización A, B, C \ en \ mathbb {Z} _ {2} [G]}$ $a B C$ ${\ estilo de texto {\ frac {7}{8}}}$

Para comprobar la asociatividad se eligen aleatoriamente , para lo cual . Tal verificación se puede realizar en el tiempo , y para lograr una probabilidad de error que no exceda , basta con realizar las verificaciones, lo que da el tiempo total de ejecución [15] . ${\ estilo de visualización A, B, C \ en \ mathbb {Z} _ {2} [G]}$ $A\cdot (B\cdot C)=(A\cdot B)\cdot C$ $O(n^{2})$ $\delta$ ${\ estilo de visualización \ log _ {8/7} \ delta ^ {-1}}$ ${\textstyle O\left(n^{2}\log \delta ^{-1}\right)}$

Operaciones arbitrarias

El enfoque de Rajagopalan y Shulman se puede generalizar para probar identidades generales, siempre que cada variable ocurra exactamente una vez en los lados izquierdo y derecho de la identidad [16] .

Por ejemplo, podemos considerar un conjunto sobre cuyos elementos se especifican tres operaciones: "unión" , "intersección" y "suma" . Hay que comprobar eso . Para ello, podemos considerar las operaciones inducidas $GRAMO$ ${\ estilo de visualización a \ taza b}$ $a\cap b$ ${\ barra {a}}$ ${\overline {a\cap (b\cup c)))={\overline {a))\cup ({\overline {b))\cap {\overline {c)))$ ${\ estilo de visualización \ mathbb {Z} _ {2} [G]}$

{\textstyle A\cup B=\sum \limits _{g\in G}\left(\bigoplus \limits _{x\cup y=g}a_{x}b_{y}\right)g}

, y

{\textstyle A\cap B=\sum \limits _{g\in G}\left(\bigoplus \limits _{x\cap y=g}a_{x}b_{y}\right)g}

{\bar {A}}=\sum \limits _{g\in G}{\bar {a}}_{g}g

y verifique que para estas operaciones en sea verdadero . En la forma más general, el procedimiento se puede caracterizar por el siguiente teorema [16] : ${\ estilo de visualización \ mathbb {Z} _ {2} [G]}$ ${\overline {A\cap (B\cup C)}}={\overline {A}}\cup ({\overline {B}}\cap {\overline {C)))$

Sean conjuntos finitos, y sea un conjunto de operaciones definidas sobre productos cartesianos finitos de estos conjuntos tal que la operación se define sobre el conjunto , donde es la aridad de la operación . Entonces la verificación de la verdad de la identidad compuesta por estas operaciones, tal que cada variable ocurre en sus partes izquierda y derecha exactamente una vez, puede realizarse en el tiempo , donde es el mayor tamaño posible del dominio de definición , es el número total de operaciones utilizadas en la identidad, es el número total de variables, es la mayor probabilidad de error permitida. ${\displaystyle D_{1},\puntos,D_{k))$ ${\ estilo de visualización \ circ _ {1}, \ puntos, \ circ _ {m}}$ ${\ estilo de visualización \ circ _ {j}}$ ${\displaystyle D_{\sigma (j,1)}\times \dots \times D_{\sigma (j,c_{j)))))$ ${\ Displaystyle c_ {j}}$ ${\ estilo de visualización \ circ _ {j}}$ $O(2^{k}lM\log\delta^{-1})$ ${\textstyle M=\max _{j}\left(\vert D_{\sigma (j,1)}\vert \cdot \ldots \cdot \vert D_{\sigma (j,c_{j})}\ vert\derecha)}$ ${\ estilo de visualización \ circ _ {j}}$ $yo$ $k$ $\delta$

En el caso , la operación tiene un dominio de tamaño , y por lo tanto la complejidad computacional del procedimiento toma la forma , mientras que una verificación ingenua requeriría operaciones [16] . $|D_{1}|=\puntos =|D_{k}|=n$ ${\ estilo de visualización \ circ _ {j}}$ ${\ Displaystyle n^{c_{j))}$ $M=n^{\max c_{j))$ $O(2^{k}ln^{\max c_{j))\log \delta ^{-1})$ $O(ln^{k})$

Este resultado se puede mejorar si en cambio consideramos el álgebra para un número primo . En este caso, según el lema de Schwarz-Zippel , la probabilidad de refutar una identidad incorrecta en una iteración se puede mejorar de a , lo que corresponde a una probabilidad constante para y nos permite mejorar el tiempo de ejecución a [6] . ${\ estilo de visualización \ mathbb {Z} _ {2} [G]}$ ${\ estilo de visualización \ mathbb {Z} _ {p} [G]}$ $p>k$ ${\ estilo de texto {\ frac {1}{2^{k))))$ ${\estilo de texto 1-{\frac{k}{p}}}$ $p\sim (1+\varepsilon)k$ ${\ estilo de texto {\ frac {\ varepsilon} {1+\ varepsilon}}}$ $O(lM\log\delta^{-1})$

Buscar un testigo sin identidad

El algoritmo se puede modificar para encontrar un conjunto particular de variables en las que falla la identidad. Por ejemplo, considere buscar un triple no asociativo en el tiempo . Que se sepa por algunos que . Estos elementos se pueden asociar con un triple , tal que si , entonces también es igual a , y si , entonces se elige aleatoriamente entre y (de manera similar para y ). Para la probabilidad de que , la estimación de abajo seguirá siendo cierta , por lo que se puede repetir el procedimiento hasta que cada uno de los elementos tenga una unidad en una sola de las posiciones, que corresponderá a la terna no asociativa deseada en [17] . ${\ estilo de texto (a, b, c)}$ ${\textstyle O\left(n^{2}\log n\log \delta ^{-1}\right)}$ ${\ estilo de visualización A, B, C \ en \ mathbb {Z} _ {2} [G]}$ $A\cdot (B\cdot C)\neq (A\cdot B)\cdot C$ $A B C'$ ${\ estilo de visualización a_ {i} = 0}$ $a_{i}'$ ${\ estilo de visualización 0}$ ${\ estilo de visualización a_ {i} = 1}$ $a_{i}'$ ${\ estilo de visualización 0}$ $una$ $b_{i}'$ $c_{i}'$ $A'\cdot (B'\cdot C')\neq (A'\cdot B')\cdot C'$ ${\estilo de texto {\frac{1}{8}}}$ $A B C'$ $GRAMO$

Notas

↑ Lee, Magniez, Santha, 2015
↑ 12 Tarjan , 1972 , pág. 120
↑ 1 2 Lipton, Regan, 2013
↑ Es Asociativo._ _ Manual de referencia de GAP . El Grupo GAP. Consultado el 1 de septiembre de 2021. Archivado desde el original el 17 de abril de 2021.
↑ Es Asociativo._ _ Ayuda de arce . arce suave. Consultado el 14 de agosto de 2022. Archivado desde el original el 14 de abril de 2021.
↑ 1 2 Rajagopalan, Schulman, 2000 , pág. 1162
↑ 12 Sinclair , 2020
↑ 1 2 Matousek, Nešetřil, 2008
↑ Schulmann, 2020
↑ Premchand, 1984 , pág. 257
↑ Clifford, Preston, 1961 , págs. 7-8
↑ 1 2 Rajagopalan, Schulman, 2000 , págs. 1155-1156
↑ Rajagopalan, Schulman, 2000 , págs. 1160-1161
↑ Rajagopalan, Schulman, 1996
↑ 1 2 Rajagopalan, Schulman, 2000 , págs. 1156-1157
↑ 1 2 3 Rajagopalan, Schulman, 2000 , págs. 1158-1159
↑ Rajagopalan, Schulman, 2000 , págs. 1159-1160

Literatura

Clifford A., Preston G. Light's asociativity test (inglés) // The Algebraic Theory of Semigroups - USA : AMS , 1961. - Vol. 1.- Pág. 7-8. — 224 págs. - ISBN 0-8218-0271-2 - doi:10.1090/SURV/007.1
Lee T., Magniez F., Santha M. Algoritmos de consulta cuánticos mejorados para detección de triángulos y pruebas de asociatividad (inglés) // Algorithmica - Springer Science + Business Media , 2015. - Vol. 77, edición. 2.- Pág. 459-486. — 1302 pág. — ISSN 0178-4617 ; 1432-0541 - doi:10.1007/S00453-015-0084-9 - arXiv:1210.1014
Lipton R. J. , Regan K. W. Leonard Schulman: Asociatividad (inglés) // Personas, problemas y pruebas : ensayos de la carta perdida de Gödel: 2010 - 2013. - P. 297-299. — 333 pág. doi:10.1007/ 978-3-642-41422-0_57
Matoušek J. , Nešetřil J. Pruebas de asociatividad probabilística (inglés) // Invitación a las Matemáticas Discretas - 2 - NYC : OUP , 2008. - P. 388-392. — 443 pág. — ISBN 978-0-19-857043-1
Premchand S. Independencia de axiomas para conjuntos biordenados (inglés) // Semigroup Forum - Springer Science + Business Media , 1984. - vol. 28, edición. 1.- Pág. 249-263. — 397 pág. — ISSN 0037-1912 ; 1432-2137 - doi:10.1007/BF02572487
Rajagopalan S., Schulman L. J. Verificación de identidades // SIAM J. Comput . / M. Sudán - SIAM , 2000. - vol. 29, edición. 4.- Pág. 1155-1163. — 2097 pág. — ISSN 0097-5397 ; 1095-7111 - doi:10.1137/S0097539797325387
Rajagopalan S., Schulman L. J. Verificación de identidades (inglés) // Actas de la 37.ª Conferencia sobre fundamentos de la informática - 1996. - 638 p. - ISBN 0-8186-7594-2 - ISSN 0272-5428 - doi:10.1109/SFCS.1996.548520
Schulman L. Verificación de la asociatividad (inglés) // Probabilidad y algoritmos - Instituto de Tecnología de California , 2020. - P. 35-37. — 108p.
Sinclair A. Comprobación de la asociatividad (inglés) // Aleatoriedad y computación - UC Berkeley , 2020. - P. 5-6. - 7p.
Tarjan R. E. Determinar si un grupoide es un grupo // Informar . proceso. Letón. - Elsevier BV , 1972. - Vol. 1, edición. 3.- Pág. 120-124. — ISSN 0020-0190 ; 1872-6119 - doi:10.1016/0020-0190(72)90012-9