Die Komplexität von Problemen der linearen Algebra

点击翻译按钮获取中文摘要

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.