np. ?
Wyrażenia pochodzą ze zwykłej algebry w szkole średniej, ale ograniczają się do dodawania i mnożenia arytmetycznego (np. ), 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ż ; tzn. nie ani ani :
- wieloliniowe , brak mocy innych niż : jest w porządku, ale nie , i nic, co mogłoby być reprezentowane jako takie, jak w pełnym rozszerzeniu do sumy -of-produktów, np. nie ;
- 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
- brak stałych innych niż : ponownie, w pełni rozwiniętej sumie produktów, np. nie ( a + 1 ) + ( b + 1 ) ≡ a + b + 2
Czy istnieje skuteczny algorytm do ustalenia, czy dwa wyrażenia są równoważne?
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 y
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
(thm (= (+ (* x y) x y) (+ x (* y (+ x 1))) ))
? --- 325 kroków
(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.
źródło
Odpowiedzi:
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 e1,e2 e1+e2 e1e2
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: zerop1(x1,…,xn) p2(x1,…,xn)
Teraz są równoważne wtedy i tylko wtedy, gdy q jest wielomianem zerowym.p1,p2 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(x1,…,xn) x1,…,xn x1,…,xn q(x1,…,xn) , 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.p1,p2 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.Fn→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 primer and testing equivalence modulo r , i.e., in the field Z/rZ . 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.
źródło
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.a4=a2a2=a1a3 ), 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.
źródło