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

14

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 x2 ani 3x ani 4 :

  • wieloliniowe , brak mocy innych niż 1 : x+xyx1+x1y1 jest w porządku, ale nie x2+x3y4 , i nic, co mogłoby być reprezentowane jako takie, jak w pełnym rozszerzeniu do sumy -of-produktów, np. nie x(x+y)x2+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 1x+xy1.x+1.xy2x+3xya(x+y)+x(a+b)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 + 21(a+1)+(b+1)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 y(a+b)(x+y)ax+ay+bx+by
a(x+y)+b(x+y)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ówy+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.

hyperpallium
źródło
3
Pytanie tutaj wymaga wyjaśnienia. Na jakim polu działasz? Czy obiekty takie jak „ ” i „ b ” w wyrażeniach są elementami pola lub zmiennych? Czy to rzeczywiście pole (tzn. Czy dodawanie i mnożenie mają odwrotności)? Zauważ, że suma produktów nie pomaga, ponieważ ( a 1 + b 1 ) ( a 2 + b 2 ) ( a n + b n ) ma wykładniczo wiele terminów. ab(a1+b1)(a2+b2)(an+bn)
David Richerby
4
Jeśli obiektami są zmienne, a odejmowanie jest dozwolone, to zasadniczo pytasz o testowanie tożsamości wielomianowej, która ma losowy algorytm czasu wielomianowego według lematu Schwartza – Zippela . iff f ( x ) - g ( x ) = 0, a podstawową ideą jest to, że wielomian, który nie jest identyczny zero, nie ma wielu pierwiastków, więc jeśli zaczniesz zgadywać pierwiastki losowo i znaleźć wiele pierwiastków, istnieje duże prawdopodobieństwo, że twój wielomian był identyczny zero. f(x)=g(x)f(x)g(x)=0
David Richerby
2
Dziwię się, że nikt o tym nie wspominał, ale „jeśli jest w NP, nie muszę się martwić o znalezienie algorytmu wielomianowego” nie ma sensu. Każdy problem w P dotyczy także NP. Prawdopodobnie chciałeś zapytać, czy problem jest NP-zupełny (czy -hard).
Tom van der Zanden
2
Jeśli masz problemy z podstawami, nasze pytania referencyjne mogą być dla Ciebie pomocne.
Raphael
2
@hyperpallium Zanim zapytasz, czy język (tj. problem decyzyjny) jest w NP, najlepiej, jeśli zrozumiałeś, co to znaczy. Być może pomocne byłyby pytania referencyjne, z którymi łączył się Raphael.
Yuval Filmus

Odpowiedzi:

9

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.xxcce1,e2e1+e2e1e2

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)

q(x1,,xn)=p1(x1,,xn)p2(x1,,xn).

Teraz są równoważne wtedy i tylko wtedy, gdy q jest wielomianem zerowym.p1,p2q

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.qq(x1,,xn)x1,,xnx1,,xnq(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,p2qqq

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.FnF

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

D.W.
źródło
1
On the other hand, it would be hard to prove that for each identically-zero expression, there is a not-too-long proof that the expression is identically zero.
@RickyDemer, great point! Nice observation. I interpreted the question as asking about testing equivalence rather than proving it, but that's a very nice observation. (If you wanted to exhibit a proof of equivalence in practice, I suspect it's feasible to exhibit such a proof if you're willing to make cryptographic assumptions, for some definition of "proof" -- e.g., a scheme that achieves soundness in the random oracle model.)
D.W.
1
Thanks! I'm treating them as formal objects, without inverses, division or subtraction (but using high school algebra for this question; seems more likely to be already solved). Do you mean, keep choosing large random primes r, and this is treating the expressions as if they were finite fields over the underlying set of integers [0..r1]? That wiki link says there's no known sub-exponential deterministic algorithm for this zero-testing. Do you know if that applies to my problem?
hyperpallium
1
@hyperpallium, yes exactly that's what I mean. Yes, I believe that applies to your problem, too. That's why I suggested a randomized algorithm -- there are efficient randomized algorithms, even though there are no known efficient deterministic algorithms.
D.W.
As pointed out in a comment above, the OP is not working in a finite field, but rather a commutative semiring. This means that additive inverses are not guaranteed to exist, so "subtracting" the expressions to check equality with zero is not a valid operation.
apnorton
0

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.

hyperpallium
źródło