Czy istnieje skuteczny algorytm równoważności wyrażeń?

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

Wyrażenia pochodzą ze zwykłej algebry w szkole średniej, ale ograniczają się do dodawania i mnożenia arytmetycznego (np. $2+2=4; 2.3=6$ ), bez odwrotności, odejmowania lub dzielenia. Litery są zmiennymi.

Jeśli to pomoże, możemy zabronić jakiegokolwiek wyrażenia reprezentowanego przez wartości liczbowe inne niż $1$ ; tzn. nie $x^2$ ani $3x$ ani $4$ :

• wieloliniowe , brak mocy innych niż $1$ : $x+xy \equiv x^1+x^1y^1$ jest w porządku, ale nie $x^2+x^3y^4$ , i nic, co mogłoby być reprezentowane jako takie, jak w pełnym rozszerzeniu do sumy -of-produktów, np. nie $x(x+y) \equiv x^2+y$ ;
• wszystko jedno , brak innych współczynników niż : x + x y ≡ 1. x + 1. x y jest OK, ale nie 2 x + 3 x y , i nic, co mogłoby być reprezentowane jako takie, jak w pełnym rozwinięciu do suma produktów, np. nie a ( x + y ) + x ( a + b ) ≡ 2 a x + a y + b x ; i $1$$x+xy \equiv 1.x+1.xy$$2x+3xy$$a(x+y)+x(a+b) \equiv 2ax+ay+bx$
• brak stałych innych niż : ponownie, w pełni rozwiniętej sumie produktów, np. nie ( a + 1 ) + ( b + 1 ) ≡ a + b + $1$$(a+1)+(b+1) \equiv a+b+2$

Czy istnieje skuteczny algorytm do ustalenia, czy dwa wyrażenia są równoważne?$Q.$

Aby to zilustrować, oto nieefektywny algorytm brutalnej siły z czasem wykładniczym:

rozwiń oba wyrażenia w pełni do sumy produktów , które można łatwo sprawdzić pod kątem równoważności (po prostu zignoruj ​​kolejność, ponieważ dojazdy / powiązania mogą zmieniać kolejność).

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

Wydaje się, że jest to dobrze znany problem - nawet uczniowie szkół średnich uczą się ręcznych sposobów jego rozwiązania. Zostało to również rozwiązane przez automatyczne sprawdzanie / sprawdzanie twierdzeń, ale koncentrują się one na bardziej wyrafinowanych aspektach.

Oto działający internetowy automat do sprawdzania twierdzeń: http://tryacl2.org/ , który pokazuje równoważność poprzez znalezienie sekwencji dojazdów / kojarzeń / dystrybucji itp .:

? --- 188 kroków $xy+x+y=x+y(x+1)$
(thm (= (+ (* x y) x y) (+ x (* y (+ x 1))) ))

? --- 325 kroków$y+x(y+1)=x+y(x+1)$
(thm (= (+ y (* x (+ y 1))) (+ x (* y (+ x 1))) ))

To jest moje pierwsze pytanie tutaj, więc proszę dać mi znać, czy wybrałem niewłaściwe miejsce, złe tagi, niewłaściwy sposób opisywania / zadawania pytań itp. Dzięki!
Uwaga: to pytanie zostało przepisane w odpowiedzi na komentarze
Dziękujemy wszystkim respondentom! Dużo się nauczyłem.

Twój problem ogranicza się do zerowego testowania wielomianowych wielomianów, dla których istnieją wydajne algorytmy randomizowane.

Twoje wyrażenia są wielomianami wielowymiarowymi. Najwyraźniej twoje wyrażenia są zbudowane według następujących reguł: (a) jeśli jest zmienną, to x jest wyrażeniem; (b) jeśli c jest stałą, to c jest wyrażeniem; (c) jeżeli e 1 , e 2 są wyrażeniami, to e 1 + e 2 i e 1 e 2 są wyrażeniami. Jeśli rzeczywiście tak zamierzałeś, każde wyrażenie jest wielomianowym wielomianem nad zmiennymi.$x$$x$$c$$c$$e_1,e_2$$e_1+e_2$$e_1e_2$

Teraz chcesz wiedzieć, czy dwa wyrażenia są równoważne. Sprowadza się to do sprawdzenia, czy dwa wielomiany wielomianowe są równoważne: biorąc pod uwagę i p 2 ( x 1 , … , x n ) , chcesz wiedzieć, czy te dwa wielomiany są równoważne. Możesz to przetestować, odejmując je i sprawdzając, czy wynik jest identyczny: zero$p_1(x_1,\dots,x_n)$$p_2(x_1,\dots,x_n)$

Teraz są równoważne wtedy i tylko wtedy, gdy q jest wielomianem zerowym.$p_1,p_2$$q$

Testowanie, czy jest identycznie zerowe, stanowi problem testowania zerowego dla wielomianowych wielomianów. Istnieją na to wydajne algorytmy. Na przykład jeden przykładowy algorytm polega na ocenie q ( x 1 , … , x n ) przy wielu losowych wartościach x 1 , … , x n . Jeśli znajdziesz wartość x 1 , … , x n taką, że q ( x 1 , … , x n ) nie jest identycznie zerowe, tj.$q$$q(x_1,\dots,x_n)$$x_1,\dots,x_n$$x_1,\dots,x_n$$q(x_1,\dots,x_n)$ , to wiesz, że $q$ nie są równoważne. Jeśli po wielu próbach wszystkie są równe zero, możesz dojść do wniosku, że q jest identycznie zerowe (jeśli q nie jest identycznie zerowe, prawdopodobieństwo, że wszystkie te próby dadzą zero, może być wykładniczo niskie). Liczba iteracji, które należy wykonać, zależy od stopnia q ; szczegółowe informacje można znaleźć w literaturze na temat testowania tożsamości wielomianowej.$p_1,p_2$$q$$q$$q$

Na przykład zobacz https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma i http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the- schwartz-zippel-lemma /

Algorytmy te mają zastosowanie, jeśli pracujesz nad polem skończonym. Nie zrobił tego, co field / pierścień stan pracujesz w, czy traktują tych wyrażeń jako wyrażenia formalnych (np wielomiany jako abstrakcyjne obiekty) lub jako funkcje z . Jeśli pracujesz nad skończonym polem, powyższe metody obowiązują natychmiast.$\mathbb{F}^n \to \mathbb{F}$

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.

The above is not a formal or rigorous argument. It rests on an assumption about what makes the problem difficult. But it does seem to me that combining terms only makes for an easier problem - so preventing this by the one coefficient constraint is not going to make the subset easier.