Algorithmen für Einbettungen und Homotopietheorie

Das mathematische Gebiet der Topologie beschäftigt sich mit geometrischen Formen (`topologischen Räumen`), insbesondere mit Eigenschaften, die erhalten bleiben, wenn man die Formen stetig verformt (z.B. verdreht oder dehnt, aber ohne sie zu zerreißen oder zu durchbohren). Ein klassisches Beispiel einer solcher Eigenschaft ist die Frage, ob eine Form einfach zusammenhängend ist, d.h., ob man jede ganz innerhalb der Form verlaufende geschlossene Schlaufe zu einem Punkt zusammenziehen kann (die Schlaufe darf sich dabei selbst durchdringen, aber nicht die Form verlassen)beispielsweise ist eine zweidimensionale Kugeloberfläche einfach zusammenhängend, ein Torus (Fahrradschlauch) hingegen nicht. Die algorithmischen Topologie beschäftigt sich mit der Frage, für welche topologische Eigenschaften es Algorithmen gibt, die entscheiden können, ob eine gegebene geometrische Form diese Eigenschaft hat. Beispielsweise ist es ein klassisches Resultat, dass es keinen Algorithmus gibt, der für jede gegebene geometrische Form korrekt entscheidet, ob sie einfach zusammenhängend ist oder nicht. (Für diese algorithmischen Fragestellungen geht man davon aus, dass die geometrischen Formen, die man untersuchen möchte, in einer Beschreibung vorliegen, die sich als Eingabe für einen Algorithmus eignet, beispielsweise als ein sogenannter Simplizialkomplexeiner Anleitung, wie die Form aus einfachen Bausteinen wie Dreiecken und Tetraedern zusammenbauen kann). Das vorliegende Projekt beschäftigt sich mit zwei topologischen Fragestellungen: erstens ob sich eine gegebene geometrische Form in den uns umgebenden dreidimensionalen Raum (oder in höherdimensional Räume) einbetten lässt (eventuell verzerrt und verdreht, aber ohne sich selbst zu durchdringen), und zweitens mit höherdimensionalen Verallgemeinerungen von einfachem Zusammenhang (z.B. sogennanten Homotopiegruppen). Das Ziel ist es, herauszufinden, unter welchen Voraussetzungen diese Fragestellungen algorithmisch entscheidbar bzw, unentscheidbar sind, und welche Resourcen (Zeit und Speicherplatz) dafür prinzipiell erforderlich sind. Ferner versuchen wir die geometrische Komplexität von Einbettungen und Homotopien zu quantifizieren, z.B. zu verstehen, wie sehr man eine Form schlimmstenfalls `verdrehen`, `strecken` oder `falten` muss, um sie einbetten zu können.

Ein Simplizialkomplex ist eine Anleitung, wie eine geometrische Form (ein ``tropologischer Raum'') durch Zusammenfügen von einfachen Bausteinen -- Liniensegmenten, Dreiecken, Tetraedern und deren Verallgemeinerungen, höherdimensionalen Simplizes -- konstruiert werden kann. Kann eine derart abstrakt beschriebene geometrisches Form in den dreidimensionalen Raum eingebettet werden (möglicherweise verzerrt und verdreht, aber ohne Selbstüberschneidungen)? Was geschieht, wenn wir statt des uns vertrauten dreidimensionalen Raumes Einbettungen in einen d-dimensionalen Raum betrachten? Dieses Projekt untersucht diese und verwandte klassische Fragen der Geometrie und Topologie aus dem Blickwinkel der theoretischen Informatik. Wir zeigen, dass es für manche dieser Fragen effiziente Algorithmen gibt, die sie lösen, während andere, sehr ähnliche Fragen prinzipiell (und mathematisch beweisbar) algorithmisch unlösbar sind. Überraschenderweise erlauben unsere Methoden auch Schlussfolgerungen auf mathematische Probleme, die mit "höheren Dimensionen" nichts zu tun zu haben scheinen, wie zum Beispiel die folgende Aussage. Für jede positive ganze Zahl n kann jede konvexe Region in der Ebene in n konvexe Teile von gleicher Fläche und gleichem Umfang unterteilt werden. (Eine Region ist konvex, falls für je zwei beliebige zu der Region gehörende Punkte auch die gesamte Strecke zwischen den beiden Punkten komplett in der Region enthalten ist.)