Gibt es einen effizienten Algorithmus für die Ausdrucksäquivalenz?

14

z xy+x+y=x+y(x+1) ?

Die Ausdrücke stammen aus der gewöhnlichen High-School-Algebra, beschränken sich jedoch auf arithmetische Addition und Multiplikation (z. B. ), ohne Inverse, Subtraktion oder Division. Buchstaben sind Variablen.2+2=4;2.3=6

Wenn es hilft, können wir jeden Ausdruck verbieten, der mit anderen numerischen Werten als . dh nicht noch noch :x 2 3 x 41x23x4

  • Multilinear , keine anderen Potenzen als : x + x y x 1 + x 1 y 1 ist in Ordnung, aber nicht x 2 + x 3 y 4 , und nichts, was als das dargestellt werden könnte, wie in einer vollständigen Ausdehnung zur Summe -der-Produkte, zB nicht x ( x + y ) x 2 + y ; 1x+xyx1+x1y1x2+x3y4x(x+y)x2+y
  • alle eins , keine anderen Koeffizienten als : x + x y 1. x + 1. x y ist OK, aber nicht 2 x + 3 x y , und nichts, was als das dargestellt werden könnte, wie bei einer vollen Ausdehnung auf Produktsumme zB nicht a ( x + y ) + x ( a + b ) 2 a x + a y + b x ; und 1x+xy1.x+1.xy2x+3xya(x+y)+x(a+b)2ax+ay+bx
  • Keine anderen Konstanten als : Wiederum in der vollständig erweiterten Produktsumme, z. B. nicht ( a + 1 ) + ( b + 1 ) a + b + 21(a+1)+(b+1)a+b+2

Gibt es einen effizienten Algorithmus, um festzustellen, ob zwei Ausdrücke äquivalent sind?Q.


Zur Veranschaulichung hier ein ineffizienter Brute-Force-Algorithmus mit exponentieller Zeit:

Erweitern Sie beide Ausdrücke vollständig zu einer Produktsumme , die leicht auf Gleichwertigkeit überprüft werden kann (ignorieren Sie einfach die Reihenfolge, da Commute / Associate die Reihenfolge ändern kann).

zB
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


Dies scheint ein bekanntes Problem zu sein - selbst Schülern werden manuelle Lösungswege vermittelt. Es wird auch durch automatisierte Theoremprüfer / -prüfer gelöst, die sich jedoch auf komplexere Aspekte konzentrieren.

Hier ist ein funktionierender automatisierter Online-Theorembeweiser: http://tryacl2.org/ , der die Gleichwertigkeit zeigt, indem eine Abfolge von Commute / Associate / Distribute usw. gefunden wird:

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

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

Dies ist meine erste Frage, also lass es mich bitte wissen, wenn ich den falschen Ort, die falschen Tags, die falsche Art zu beschreiben / zu fragen usw. gewählt habe. Danke!
NB: Diese Frage wurde als Antwort auf Kommentare umgeschrieben.
Vielen Dank an alle Antwortenden! Ich habe viel gelernt.

Hyperpallium
quelle
3
Die Frage hier bedarf einer Klärung. Auf welchem ​​Gebiet operieren Sie? Sind die Objekte wie " " und " b " in Ihren Ausdrücken Elemente des Feldes oder Variablen? Ist es tatsächlich ein Feld (dh haben Addition und Multiplikation Inverse)? Man beachte, dass die Summe der Produkte nicht hilft, weil ( a 1 + b 1 ) ( a 2 + b 2 ) ( a n + b n ) exponentiell viele Terme hat. ab(a1+b1)(a2+b2)(an+bn)
David Richerby
4
Wenn es sich bei den Objekten um Variablen handelt und Subtraktion zulässig ist, fragen Sie im Wesentlichen nach Polynomidentitätstests, die einen randomisierten Polynomzeitalgorithmus nach dem Schwartz-Zippel-Lemma haben . iff f ( x ) - g ( x ) = 0 und die Grundidee ist, dass ein Polynom, das nicht gleich Null ist, nicht viele Wurzeln hat Wenn Sie viele Wurzeln finden, besteht eine hohe Wahrscheinlichkeit, dass Ihr Polynom identisch Null war. f(x)=g(x)f(x)g(x)=0
David Richerby
2
Ich bin überrascht, dass dies noch niemand erwähnt hat, aber "wenn es in NP ist, muss ich mir keine Sorgen machen, einen Polynomalgorithmus zu finden", ergibt keinen Sinn. Jedes Problem in P ist auch in NP. Sie wollten wahrscheinlich fragen, ob das Problem NP-vollständig (oder -hart) ist.
Tom van der Zanden
2
Wenn Sie mit den Grundlagen zu kämpfen haben, können unsere Referenzfragen hilfreich für Sie sein.
Raphael
2
@hyperpallium Bevor Sie fragen, ob eine Sprache (dh ein Entscheidungsproblem) in NP vorliegt, sollten Sie verstehen, was dies bedeutet. Vielleicht würden die Referenzfragen, mit denen Raphael verbunden war, helfen.
Yuval Filmus

Antworten:

9

Ihr Problem reduziert sich auf Null beim Testen multivariater Polynome, für die es effiziente randomisierte Algorithmen gibt.

xxcce1,e2e1+e2e1e2

Nun möchten Sie wissen, ob zwei Ausdrücke äquivalent sind. Dies läuft darauf hinaus, zu testen, ob zwei multivariate Polynome äquivalent sind: Wenn und p 2 ( x 1 , , x n ) gegeben sind , möchten Sie wissen, ob diese beiden Polynome äquivalent sind. Sie können dies testen, indem Sie sie subtrahieren und prüfen, ob das Ergebnis identisch Null ist: definep1(x1,,xn)p2(x1,,xn)

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

Jetzt sind genau dann äquivalent, wenn q das Nullpolynom ist.p1,p2q

Das Testen, ob identisch Null ist, ist das Nulltestproblem für multivariate Polynome. Dafür gibt es effiziente Algorithmen. Beispielsweise besteht ein beispielhafter Algorithmus darin, q ( x 1 , ... , x n ) bei vielen Zufallswerten von x 1 , ... , x n zu bewerten . Wenn Sie einen Wert von x 1 , , x n finden, so dass q ( x 1 , , x n ) , dann wissen Sie, dass qqq(x1,,xn)x1,,xnx1,,xnq(x1,,xn)qp1,p2qqq

Siehe zum Beispiel https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma und http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the- Schwartz-Zippel-Lemma /

FnF

rrZ/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.
quelle
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.
DW
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
quelle