Lösbarkeit und Komplexität im Turingmaschinenmodell von numerischen Problemen über Funktionenräumen

• Antragsteller: Professor Dr. Peter Hertling
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2006 bis 2009
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 22442428

Numerische Verfahren werden oft nur in abstrakter Form beschrieben. Bei der Implementierung auf digitalen Computern können dann noch erhebliche Probleme auftreten. Es ist das Ziel dieses Projekts, numerische Probleme auf ihre Lösbarkeit und 2 Komplexität im Turingmaschinenmodell hin zu untersuchen, dem in der Berechenbarkeitstheorie und Komplexitätstheorie vorwiegend benutzten theoretischen Modell für digitale Computer. Dabei soll in diesem Projekt der Schwerpunkt auf Problemen liegen, die in der Information-Based Complexity untersucht werden, einer Teildisziplin der numerischen Mathematik, die mit einem real number-Modell arbeitet. Es soll überprüft werden, ob und inwieweit sich Ergebnisse der Information-Based Complexity zur Komplexität von numerischen Problemen in real number-Modell sauf das Turingmaschinenmodell übertragen lassen Hierzu sind zuerst einmal grundlegende berechenbarkeitstheoretische Fragen zur numerischen Mathematik, zur Maßtheorie und zur Funktionalanalysis zu klären. Anschließend sollen auch komplexitätstheoretische Fragen beantwortet werden.

• DFG-Verfahren: Sachbeihilfen