Algorithmen für direkte Produkte

In den letzten zehn Jaren haben algebraische Methoden einen zentralen Beitrag in der Erforschung sogannter Constraint-Satisfaction-Problems (CSP) aus der Informatik und dem Gebiet der Künstlichen Intelligenz geleistet. Diese Familie von Problemen enthält eine Vielzahl klassischer Entscheidungsprobleme, wie zum Beispiel, die Erfüllbarkeit Boolescher Ausdrücke, Graphenfärbeprobleme oder die Lösbarkeit linearer Gleichungssysteme. Nach einer Vermutung von T. Feder und M. Vardi aus 1993 sollte die Klasse aller CSP in genau zwei Teile zerfallen: solche die in polynomialer Zeit lösbar sind (wie lineare Gleichungen) und solche die NP-vollständig sind (wie die Frage ob ein Graph sich mit 3 Farben färben lässt). NP-vollständige Probleme sind die schwierigsten Probleme, für die sich die Korrektheit einer gegebenen Lösung in polynomialer Zeit verifizieren lässt. Es ist jedoch nicht bekannt, wie eine solche Lösung effizient gefunden werden kann. Zu jedem CSP kann eine algebraische Struktur konstruiert werden, sodass das Lösen des CSP sich auf das Bestimmen des Durchschnitts von Unteralgebren eines direkten Produkts dieser Algebra reduziert (Unter einer Algebra verstehen wir hier einfach eine Menge mit Operationen). Diese entscheidende Beobachtung von A. Bulatov, P. Jeavons und A. Krokhin von 2000 macht algebraische Methoden in diesem Bereich der Informatik anwendbar. Der Wunsch, CSP zu analysieren und zu lösen, führt zu offenen Fragen, wie man Unteralgebren direkter Produkte darstellen und wie man mit ihnen rechnen kann. Zum Beispiel, wie findet man Generatoren, überprüft Zugehörigkeit oder berechnet Durchschnitte? Ziel dieses Forschungsprojekts ist es, effiziente Methoden zum Rechnen mit direkten Produkten und ihren Unterstrukturen zu finden. Es vereint also klassische allgemeine Algebra mit Informatik. Wir entwickeln Algorithmen, wie solche zum Lösen linearer Gleichungen in Linearer Algebra, für eine viel grössere Klasse von algebraischen Strukturen, die auch Gruppen und Verbände einschliesst. Insbesonders geht es dabei um folgende Fragestellungen für Unteralgebren direkter Produckte: 1. Finde kleine Mengen von Erzeugern. 2. Überprüfe ob ein Element in einer Unteralgebra, die durch Erzeuger gegeben ist, enthalten ist. 3. Bestimme Erzeuger für den Durchschnitt zweier Unteralgebren, die durch Erzeuger gegeben sind. Algorithmen für diese Probleme sind grundlegend um Gleichungen über algebraische Strukturen zu lösen. Sie würden zusätzlich einen neuen und transparenten Zugang zu CSP bieten. Zuletzt sollen die entwickelten Methoden in bestehenden Computer-Algebra-Programmen, wie GAP, implementiert werden.

Relationen gibt es überall. In der Mathematik kann man sie als Paare darstellen (z.B., a ist kleiner als b) oder allgemeiner als Tupel (z.B., jede der Webseiten a, b, c verweist auf die anderen beiden). Viele Planungsprobleme in der Informatik und der Künstlichen Intelligenz lassen sich mittels Relationen als so- genannte Constraint Satisfaction Problems (CSP) formulieren. Zum Beispiel hantiert man beim Erstellen eines Zeitplans mit Relationen. Ziel dieses Projekts war es, dies mit Algebra effizienter zu gestalten.Dazu kann man für jede Relation spezielle Operationen finden, die uns erlauben, mit den Tupeln zu rechnen. So werden Relationen zu algebraischen Strukturen (genauer gesagt zu Unterstrukturen direkter Produkte von Algebren). Das macht es leichter, Muster zu erkennen, Relationen zu vergleichen, Tupel mit bestimmten Eigenschaften zu finden und möglicherweise eine große Relation mit nur wenig Tupeln (den Erzeugern) darzustellen.Gemeinsam mit Mathematikern und Informatikern aus Kanada, Spanien, Großbritannien und den USA forschte unser Projektteam an der JKU Linz im wesentlichen an drei Fragen:1. Wie findet man kurze Darstellungen von Relationen? Mit N. Ru?kuc (St. Andrews) untersuchten wir, ob und wie man unendliche Strukturen in direkten Produkten effizient mit endlich vielen Erzeugern beschreiben kann.2. Wie rechnet man mit den Erzeugern von Relationen? Erzeuger geben eine kurze Darstellung von Relationen, aber haben den Nachteil, dass mit ihnen grundlegende Aufgaben wie das Testen, ob ein Tupel in der Relation liegt, das Bestimmen von Durchschnitten von Relationen etc., oft sehr komplex wer- den. Im Allgemeinen wachst der Aufwand dafür exponentiell mit der Länge der betrachteten Tupel. Mit A. Bulatov (Vancouver) und . Szendrei (Boulder) zeigten wir für die sogenannten Algebren mit wenig Unterpotenzen, dass sich diese Probleme schon in nicht-deterministischer polynomialer Zeit (NP) lösen lassen. Unter zusätzlichen Bedingungen fanden wir noch effizientere Algorithmen, die nur polynomiale Zeit (P) benötigen.3. Was sind die Anwendungen? Diese theoretischen Grundlagen dienten schließlich zur Analyse einer Verallgemeinerung von CSP, nämlich QuantifiedConstraint Satisfaction Problems (QCSP), die etwa bei der Überprüfung von Computer-Hardware eine Rolle spielen. Für bestimmte Klassen von QCSP fan- den wir mit H. Chen (San Sebastian) neue Algorithmen und klassifizierten ihre Komplexität: die von uns betrachteten Probleme sind entweder in P (leicht), NP-vollständig (schwer) oder PSPACE-vollständig (sehr schwer).