Die Komplexität von Problemen der linearen Algebra

• Applicant: Professor Dr. Thomas Thierauf
• Subject Area: Theoretical Computer Science
• Term: from 2000 to 2005
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants