BannerBannerBanner

Geometrische Komplexitätstheorie


Geometrische Entscheidungsprobleme

In der computergestützten Geometrie ist man nicht selten an algorithmischen Entscheidungsproblemen interessiert: "Ist ein Graph planar zeichenbar?", "Lässt sich ein Polytop mit einer gegebenen Anzahl Simplizes füllen?", "Lässt sich der Seitenverband eines Polytopes geometrisch realisieren?", "Ist ein Matroid orientierbar?", "Ist ein orientiertes Matroid realisierbar?", "Lässt sich eine Instanz einer dynamischen Geometriekonstruktion stetig in eine andere überführen?"

Inf.gif
Teilkonstruktion des Universalitätssatzes für Polytope
All diese Fragestellungen haben gemeinsam, dass die Problemstellung sich auf einfache Weise kombinatorisch codieren lässt und die Ausgabe eine einfache ja/nein Antwort ist. Bis auf das erste Problem stellen sich alle genannten Probleme als mindestens NP-schwer heraus, wie ich und einige meiner co-Autoren in verschiedenen Arbeiten zeigen konnte. Typischerweise lassen sich derartige Komplexitätsbeweise aus kleinen aber nützlichen "Gadgets" zusammensetzen. Man beginnt mit kleinen Bausteinen einer bestimmten Kategorie von geometrischen Objekten, die einen gewissen Effekt isolieren (z.B. als logischer Schalter dienen können). Durch geeignete Kombination mehrerer solcher Gadgets gelingt es immer komplexere logische Strukturen in einer Konstruktion zu vereinigen. So lange, bis man schliesslich ein als schwer bekanntes Vergleichsproblem vollständig in die geometrische Situation eingebettet hat. Stellvertretend seine hier einige Komplexitätsergebnisse ausgeführt.

Universalitätssatz für 4-Polytope

Im Rahmen meiner Habilitationsschrifft (siehe Springer Lecture Notes in Mathematics 1643) gelang es mir zu zeigen, dass es NP-schwer ist, zu testen, ob der Seitenverband einer kombinatorischen 3-Späre geometrisch als Polytop realisierbar ist. Mehr noch, das Problem ist sogar so schwer, wie das Lösen beliebiger polynomialer Ungleichungssysteme. Darüber hinaus kann man zeigen, dass zum Realisieren aller 4-Polytope alle algebraischen Zahlen benötigt werden und dass die Realisierungsräume dabei die Komplexität beliebiger semialgebrischer Varietäten annehmen können.

Bitte schalten Sie Java ein, um eine Cinderella-Konstruktion zu sehen.
Ein geometrisches Safe-Schloss

Minimales Triangulieren von 3-Polytopen ist schwer

Gemeinsam mit A. Below und J. de Loera gelang es zu zeigen, dass es NP-schwer ist, ein 3 dimensionales Polytop minimal zu triangulieren. D.h. für jedes logische Erfüllbarkeitsproblem kann man ein konkretes 3-dimensionales Polytop P und eine Zahl k angeben, so dass die Entscheidung, ob P mit k oder weniger Simplizes trianguliert werden kann, äquivalent zur Lösung des Erfüllbarkeitsproblems ist.

Erreichbarkeit in dynamischer Geometrie

Auch im Bereich der dynamischen Geometrie gibt es hoch interessante Erfüllbarkeitsprobleme, die sich als schwer herausstellen. Durch Mehrdeutigkeiten in einer Konstruktion (siehe den Absatz über Dynamische Geometrie) kann man leicht zu einer Konstruktion mehrere geometrisch verschiedene Instanzen angeben. Es stellt sich die natürliche Frage, ob man eine Instanz einer Konstruktion stetig in eine Andere überführen kann. Gemeinsam mit Ulrich Kortenkamp gelang es zu zeigen, dass dieses Problemm (selbst unter stark einschränkenden Annahmen an die erlaubten Konstruktionsschritte) im Allgemeinen beweisbar schwer ist. Um ein Gefühl für die Komplexität des Problemes versuchen sie einmal in der neben stehenden Konstruktion allein durch Bewegen der grünen Punkte die Rolle der grünen und der roten Winkelhalbierenden zu vertauschen.