Die Komplexität von Problemen der linearen Algebra

• Antragsteller: Professor Dr. Thomas Thierauf
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2000 bis 2005
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5248200

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. Interessanterweise besteht ein sehr enger Zusammenhang zu Anzahlproblemen auf Graphen. Dadurch lassen sich diese 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 Graphproblemen, 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.

• DFG-Verfahren: Sachbeihilfen