Das Projekt ist an der Universität Ulm angesiedelt, mit Thanh Minh Hoang als Mitarbeiter.
Zusammenfassung.
Es soll die Komplexität von Problemen in der linearen Algebra
untersucht werden.
Typische Probleme sind die Berechnung
der Inversen,
der Determinanten,
des charakteristischen Polynoms oder
von Potenzen einer Matrix.
Effiziente Lösungswege für Probleme aus der linearen Algebra zu finden, ist seit langem Thema der Forschung. Insbesondere die Determinanten-Berechnung findet viel Aufmerksamkeit. Csanky gab den ersten parallelen Algorithmus für die Determinante an. Cook definierte die Klasse Det aller Problem die auf die Determinante reduzierbar sind, und gab mehrere vollständige Probleme für Det an. Damm, Toda, Vinay und Valiant gelang es (unabhängig voneinander) einen sehr engen Zusammenhang der Determinanten zu Anzahlproblemen auf Graphen (z.B.: bestimme in einem Graph die Anzahl der Wege von Knoten s zu Knoten t) herzustellen. Dadurch lassen sich viele algebraischen Probleme in natürlicher Weise in Komplexitätsklassen fassen, die über die Anzahl von akzeptierenden Rechnungen von logarithmisch platzbeschränkten Turingmaschinen definiert sind.
Damit ist die Frage nach der Komplexität algebraischer Problemstellungen direkt gekoppelt an die Komplexität von Problemen auf Graphen, und diese wiederum an die Eigenschaften und Inklusionsbeziehungen von Komplexitätsklassen, die über logarithmische Platzschranken definiert sind. Es bieten sich somit verschiedene Angriffspunkte an, um die Komplexität algebraischer Problemstellungen zu verstehen.