Existe-t-il un algorithme efficace pour l'équivalence d'expression?

par exemple $xy+x+y=x+y(x+1)$ ?

Les expressions proviennent de l'algèbre ordinaire du secondaire, mais se limitent à l'addition et à la multiplication arithmétiques (par exemple $2+2=4; 2.3=6$ ), sans inverses, soustraction ou division. Les lettres sont des variables.

Si cela aide, nous pouvons interdire toute expression représentable avec des valeurs numériques autres que ; c'est-à-dire pas x 2 ni 3 x ni 4 :$1$$x^2$$3x$$4$

• multilinéaire , pas de puissances autres que : x + x y ≡ x 1 + x 1 y 1 est OK, mais pas x 2 + x 3 y 4 , et rien de ce qui pourrait être représenté comme cela, comme dans une expansion complète pour résumer -des produits, par exemple pas 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$
• tout un , pas de coefficients autres que : x + x y ≡ 1. x + 1. x y est OK, mais pas 2 x + 3 x y , et rien de ce qui pourrait être représenté comme cela, comme dans une expansion complète à somme des produits, par exemple pas a ( x + y ) + x ( a + b ) ≡ 2 a x + a y + b x ; et $1$$x+xy \equiv 1.x+1.xy$$2x+3xy$$a(x+y)+x(a+b) \equiv 2ax+ay+bx$
• pas de constantes autres que : encore une fois, dans la somme des produits entièrement développée, par exemple pas ( a + 1 ) + ( b + 1 ) ≡ a + b + $1$$(a+1)+(b+1) \equiv a+b+2$

Existe-t-il un algorithme efficace pour déterminer si deux expressions sont équivalentes?$Q.$

Pour illustrer, voici un algorithme de force brute inefficace avec un temps exponentiel:

étendre complètement les deux expressions à la somme des produits , dont l'équivalence peut facilement être vérifiée (il suffit d'ignorer l'ordre, car les déplacements / associés peuvent être réorganisés).

ex.
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$

Cela semble un problème bien connu - même les élèves du secondaire apprennent des moyens manuels de le résoudre. Il est également résolu par des vérificateurs / vérificateurs de théorèmes automatisés, mais ils se concentrent sur des aspects plus sophistiqués.

Voici un prouveur de théorème automatisé en ligne: http://tryacl2.org/ , qui montre l'équivalence en trouvant une séquence de trajet / associer / distribuer etc:

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

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

Ceci est ma première question ici, alors faites-moi savoir si j'ai choisi le mauvais endroit, les mauvaises balises, la mauvaise façon de décrire / demander, etc. Merci!
NB: cette question a été réécrite en réponse aux commentaires
Merci à tous les répondants! J'ai beaucoup appris.

Votre problème se réduit à zéro test de polynômes multivariés, pour lesquels il existe des algorithmes randomisés efficaces.

Vos expressions sont toutes des polynômes multivariés. Apparemment, vos expressions sont construites selon les règles suivantes: (a) si est une variable, alors x est une expression; (b) si c est une constante, alors c est une expression; (c) si e 1 , e 2 sont des expressions, alors e 1 + e 2 et e 1 e 2 sont des expressions. Si c'est bien ce que vous vouliez, chaque expression est un polynôme multivarié sur les variables.$x$$x$$c$$c$$e_1,e_2$$e_1+e_2$$e_1e_2$

Maintenant, vous voulez savoir si deux expressions sont équivalentes. Cela revient à tester si deux polynômes multivariés sont équivalents: étant donné et p 2 ( x 1 , … , x n ) , vous voulez savoir si ces deux polynômes sont équivalents. Vous pouvez tester cela en les soustrayant et en vérifiant si le résultat est identique à zéro: définir$p_1(x_1,\dots,x_n)$$p_2(x_1,\dots,x_n)$

$p_1,p_2$$q$

$q$$q(x_1,\dots,x_n)$$x_1,\dots,x_n$$x_1,\dots,x_n$$q(x_1,\dots,x_n)$$q$$p_1,p_2$$q$ est identique à zéro (si $q$n'est pas identique à zéro, la probabilité que tous ces essais donnent zéro peut être rendue exponentiellement faible). Le nombre d'itérations que vous devez effectuer est lié au degré de$q$; voir la littérature sur les tests d'identité polynomiale pour plus de détails.

Par exemple, voir https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma et http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the- schwartz-zippel-lemma /

These algorithms apply if you are working over a finite field. You didn't state what field/ring you are working in, and whether you are are treating these expressions as formal expressions (e.g., polynomials as abstract objects) or as functions from $\mathbb{F}^n \to \mathbb{F}$. If you are working over a finite field, the methods above apply immediately.

If you're treating the expressions as formal objects, then your expressions are equivalent to multivariate polynomials with integer coefficients. You can test equivalence of these by choosing a large random prime $r$ and testing equivalence modulo $r$, i.e., in the field $\mathbb{Z}/r\mathbb{Z}$. Repeat this polynomially many times, with different random values of $r$, and you should get an efficient randomized algorithm for testing equivalence of these formal expressions.

To follow up on the one-power, one-coefficent and one-constants constraints in the question:

These define a subset the problem of polynomial identity testing. Clearly, they can be solved with a technique that solves the general problem. The question is whether they form a subset that is more easily solved.

one-coefficient: in problems without this, terms might be combined, making the problem easier. Consider the Binomial Theorem/Pascal's triangle for $(a+b)^n$. This can be expanded one factor at a time, producing terms with overlapping orders e.g. $(a+b)(a+b) = aa+ab+ab+bb = aa+2ab+bb$ The fewer terms make it easier to expand with the next factor: $(aa+2ab+bb)(a+b) = aaa+2aab+abb + aab+2abb+bbb = aaa+3aab+3abb+bbb$ and again terms are combined, making a smaller simpler problem. This combining of terms is a form of dynamic programming.

That is, the possibility of combining terms, creating a non-one coefficient, makes the problem easier not harder.

(Although there is more work in calculation in multiplying non-one coefficients)

non-one constants are included in the above argument by considering constants as variables with zero exponent.

one-power I don't think this makes any difference. Although non-one exponents can be created in more than one way (e.g. $a^4=a^2a^2=a^1a^3$), and this can lead to overlap and combination (as in the Binomial Theorm/Pascal's triangle above), actual combination is only possible if non-one coefficients are allowed.

Ce qui précède n'est pas un argument formel ou rigoureux. Elle repose sur une hypothèse sur ce qui rend le problème difficile. Mais il ne me semble que la combinaison de termes fait que pour un problème plus facile - empêchant ainsi ce par le un coefficient de contrainte ne va pas rendre le sous - ensemble plus facile.