Assoziativität einer Verknüpfung feststellen

Neue Frage »

durst Auf diesen Beitrag antworten »
Assoziativität einer Verknüpfung feststellen
Meine Frage:
Es sei eine Verknüpfung auf einer endlichen (großen) n-elementigen Menge gegeben, z.B. durch Verknüpfungstafel. Gibt es einen effizienten Algorithmus, um die Assoziativität der Verknüpfung zu prüfen, ohne alle n^3 Kombinationen zu prüfen?

Meine Ideen:
Ich habe dazu noch keine Idee. Schön wäre eine Lösung die mit dem Aufwand n^2 auskommt, wie bei der Kommutativität.

Also ein paar einfache Gedanken dazu hatte ich schon. Wenn es Elemente a (und c) gibt, mit a*x = a oder x*a = a oder a*x = c oder x*a = c für alle x, also eine Zeile oder eine Spalte in der Tabelle ist konstant oder gleich der Eingangszeile bzw. -spalte, dann kann ich mir für diese Elemente a die komplette Prüfung sparen. Das ist z.B. bei der normalen Multiplikation mit den Elementen 0 und 1 so. Das reduziert den Gesamtaufwand aber kaum, es bleibt bei O(n^3).

Willkommen im Matheboard!
Ich hab die beiden Beiträge zusammengefasst, damit es nicht so aussieht, als ob schon jemand antwortet.

Viele Grüße
Steffen
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »