*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 12
Freitag, 22.09.2000, 17.30–17.50 Uhr, WIL C 102

Entscheidungskomplexität in Dynamischer Geometrie

Ulrich Kortenkamp, Freie Universität Berlin

Geometrische Straight-Line-Programme (GSP) sind ein Mittel, um geometrische Konstruktionen und ihre impliziten Uneindeutigkeiten zu beschreiben, und können als analytisches Analogon zur Beschreibung von Polynomen mit herkömmlichen Straight-Line-Programmen (SLP) aufgefasst werden. In diesem Vortrag widmen wir uns der algorithmischen Komplexität der Frage, ob zwei Instanzen eines GSP durch einen stetigen Pfad miteinander verbunden sind oder nicht. Diese Frage taucht zum Beispiel bei der Erzeugung von zufälligen Instanzen zum randomisierten Beweisen von geometrischen Sätzen auf.

(Gemeinsame Arbeit mit Jürgen Richter-Gebert).