Computational complexity, topology, and singularities

• Applicant: Professor Dr. Peter Bürgisser
• Subject Area: Mathematics
• Term: from 2002 to 2006
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5379865

Eine komplizierte geometrische, topologische oder kombinatorische Struktur eines algebraischen Berechnungsproblems kann oft als Ursache für eine grosse algorithmische Komplexität identifiziert werden. Diese Idee wurde von Strassen mit Hilfe des algebraisch-geometrischen Grad erstmals erfolgreich in die Tat umgesetzt Durch Arbeiten von Ben-Or, Björner, Lovász und Yao ist bekannt, dass auch topologische Invarianten wie Bettizahlen untere Schranken liefern. Diese Schranken wurden bisher fast ausschließlich auf lineare Probleme (Arrangements) angewandt. Ein weiterer Ansatz zur Verwendung topologischer Invarianten geht auf Smale und Vassiliev zurück. In diesem Forschungsvorhaben möchte der Antragsteller die Tragweite topologischer Methoden für den Beweis unterer Komplexitätsschranken systematisch ausloten. Zunächst soll geklärt werden, inwieweit die bereits vorgeschlagenen Schranken bei nichtlinearen Problemen greifen. Dazu sind Verfahren zu studieren bzw. weiterzuentwickeln, welche die Bettizahlen spezifischer singulärer algebraischer Varietäten berechnen. In einem zweiten Schritt sollen durch Verwendung feinerer Invarianten neue untere Schranken mit neuen Anwendungen erschlossen werden. Weiterhin soll untersucht werden, in welchem Umfang die gewonnenen Schranken in randomisierten Berechnungsmodellen gültig bleiben.

• DFG Programme: Research Grants