¿Existe un algoritmo eficiente para la equivalencia de expresión?

ej. ?$xy+x+y=x+y(x+1)$

Las expresiones son del álgebra ordinaria de la escuela secundaria, pero están restringidas a la suma y multiplicación aritmética (por ejemplo, ), sin inversos, restas o divisiones. Las letras son variables.$2+2=4; 2.3=6$

Si ayuda, podemos prohibir cualquier expresión representable con valores numéricos distintos de ; es decir, no x 2 ni 3 x ni 4 :$1$$x^2$$3x$$4$

• multilineal , no hay potencias distintas a : x + x y ≡ x 1 + x 1 y 1 está bien, pero no x 2 + x 3 y 4 , y nada que pueda representarse como eso, como en una expansión completa para sumar -de-productos, por ejemplo, no x ( x + y ) ≡ x 2 + y ; $1$$x+xy \equiv x^1+x^1y^1$$x^2+x^3y^4$$x(x+y) \equiv x^2+y$
• todo uno , sin coeficientes que no sean : x + x y ≡ 1. x + 1. x y está bien, pero no 2 x + 3 x y , y no hay nada que pueda representarse como eso, como en una expansión completa para suma de productos, por ejemplo, no a ( x + y ) + x ( a + b ) ≡ 2 a x + a y + b x ; y $1$$x+xy \equiv 1.x+1.xy$$2x+3xy$$a(x+y)+x(a+b) \equiv 2ax+ay+bx$
• sin constantes que no sean : nuevamente, en la suma de productos completamente expandida, por ejemplo, no ( a + 1 ) + ( b + 1 ) ≡ a + b + $1$$(a+1)+(b+1) \equiv a+b+2$

¿Existe un algoritmo eficiente para determinar si dos expresiones son equivalentes?$Q.$

Para ilustrar, aquí hay un algoritmo de fuerza bruta ineficiente con tiempo exponencial:

expanda ambas expresiones completamente a la suma de productos , que pueden verificarse fácilmente para determinar la equivalencia (simplemente ignore el orden, ya que el cambio / asociado puede reordenarse).

ej.
a ( x + y ) + b ( x + y ) → a x + a y + b x + b $(a+b)(x+y) \rightarrow ax+ay+bx+by$
$a(x+y)+b(x+y) \rightarrow ax+ay+bx+by$

Este parece un problema bien conocido: incluso a los estudiantes de secundaria se les enseñan formas manuales de resolverlo. También se resuelve con probadores / verificadores de teoremas automatizados, pero se concentran en aspectos más sofisticados.

Aquí hay un probador de teoremas automatizado en línea que funciona: http://tryacl2.org/ , que muestra la equivalencia al encontrar una secuencia de conmutar / asociar / distribuir, etc.

? --- 188 pasos $xy+x+y=x+y(x+1)$
(thm (= (+ (* x y) x y) (+ x (* y (+ x 1))) ))

? --- 325 pasos$y+x(y+1)=x+y(x+1)$
(thm (= (+ y (* x (+ y 1))) (+ x (* y (+ x 1))) ))

Esta es mi primera pregunta aquí, así que avíseme si he elegido el lugar incorrecto, las etiquetas incorrectas, la forma incorrecta de describir / preguntar, etc. ¡Gracias!
NB: esta pregunta se ha reescrito en respuesta a los comentarios ¡
Gracias a todos los que respondieron! He aprendido mucho

Su problema se reduce a cero pruebas de polinomios multivariados, para los cuales existen algoritmos aleatorizados eficientes.

Sus expresiones son todos polinomios multivariados. Aparentemente, sus expresiones están formadas por las siguientes reglas: (a) si es una variable, entonces x es una expresión; (b) si c es una constante, entonces c es una expresión; (c) si e 1 , e 2 son expresiones, entonces e 1 + e 2 y e 1 e 2 son expresiones. Si eso es lo que pretendía, cada expresión es un polinomio multivariado sobre las variables.$x$$x$$c$$c$$e_1,e_2$$e_1+e_2$$e_1e_2$

Ahora, quieres saber si dos expresiones son equivalentes. Esto equivale a probar si dos polinomios multivariados son equivalentes: dado y p 2 ( x 1 , ... , x n ) , desea saber si estos dos polinomios son equivalentes. Puede probar esto restándolos y verificando si el resultado es idénticamente cero: defina$p_1(x_1,\dots,x_n)$$p_2(x_1,\dots,x_n)$

Ahora son equivalentes si y solo si q es el polinomio cero.$p_1,p_2$$q$

Probar si es idénticamente cero es el problema de prueba cero para polinomios multivariados. Hay algoritmos eficientes para eso. Por ejemplo, un algoritmo de ejemplo es evaluar q ( x 1 , ... , x n ) en muchos valores aleatorios de x 1 , ... , x n . Si encuentra un valor de x 1 , ... , x n tal que q ( x 1 , ... , x n ) , entonces sabe que $q$$q(x_1,\dots,x_n)$$x_1,\dots,x_n$$x_1,\dots,x_n$$q(x_1,\dots,x_n)$$q$no es idénticamente cero, es decir, no son equivalentes. Si después de muchas pruebas todos son cero, entonces puede concluir que q es idénticamente cero (si q no es idénticamente cero, la probabilidad de que todas esas pruebas den cero puede hacerse exponencialmente baja). El número de iteraciones que necesita hacer está relacionado con el grado de q ; ver la literatura sobre pruebas de identidad polinomial para más detalles.$p_1,p_2$$q$$q$$q$

Por ejemplo, consulte https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma y http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the- schwartz-zippel-lemma /

Estos algoritmos se aplican si está trabajando sobre un campo finito. Usted no indicó en qué campo / anillo que se está trabajando, y si usted está está tratando estas expresiones como expresiones formales (por ejemplo, polinomios como objetos abstractos) o como funciones de . Si está trabajando sobre un campo finito, los métodos anteriores se aplican inmediatamente.$\mathbb{F}^n \to \mathbb{F}$

Si está tratando las expresiones como objetos formales, entonces sus expresiones son equivalentes a polinomios multivariados con coeficientes enteros. Puede probar la equivalencia de las mismas por la elección de un primo grande aleatoria y la prueba de equivalencia módulo r , es decir, en el campo Z / r Z . Repita esto polinomialmente muchas veces, con diferentes valores aleatorios de r , y debería obtener un algoritmo aleatorio eficiente para probar la equivalencia de estas expresiones formales.$r$$r$$\mathbb{Z}/r\mathbb{Z}$$r$

Para hacer un seguimiento de las restricciones de una potencia , un coeficiente y una constante en la pregunta:

Estos definen un subconjunto del problema de la prueba de identidad polinómica. Claramente, se pueden resolver con una técnica que resuelva el problema general. La pregunta es si forman un subconjunto que se resuelve más fácilmente.

un coeficiente : en problemas sin esto, los términos pueden combinarse, lo que facilita el problema. Considere el teorema binomial / triángulo de Pascal para . Esto se puede expandir un factor a la vez, produciendo términos con órdenes superpuestas, por ejemplo ( a + b ) ( a + b ) = a a + a b + a b + b b = a a + 2 a b + b $(a+b)^n$$(a+b)(a+b) = aa+ab+ab+bb = aa+2ab+bb$Los menos términos facilitan la expansión con el siguiente factor: y nuevamente los términos se combinan, lo que hace que el problema sea más pequeño y simple. Esta combinación de términos es una forma de programación dinámica.$(aa+2ab+bb)(a+b) = aaa+2aab+abb + aab+2abb+bbb = aaa+3aab+3abb+bbb$

Es decir, la posibilidad de combinar términos, crear un coeficiente que no sea uno, hace que el problema sea más fácil y no más difícil.

(Aunque hay más trabajo en el cálculo para multiplicar coeficientes que no son uno)

las constantes que no son uno se incluyen en el argumento anterior al considerar las constantes como variables con exponente cero.

$a^4=a^2a^2=a^1a^3$

Lo anterior no es un argumento formal o riguroso. Se basa en una suposición sobre lo que dificulta el problema. Pero me parece que combinar términos solo hace que sea un problema más fácil, por lo que evitar esto mediante la restricción de un coeficiente no facilitará el subconjunto.