|
Julia Osthues

Prof. Dr. André Nies (Universität Auckland): Vortrag: Objekte grösster Komplexität in einer Klasse

Tuesday, 24.03.2015 15:00 im Raum Hörsaal M6

Mathematik und Informatik

Gegeben sei eine Klasse von Objekten zusammen mit einer Art deren Komplexität zu vergleichen. Gibt es ein kompliziertestes Objekt in der Klasse? Ist ein solches Objekt eindeutig bestimmt? Diese Fragen treten in vielen Gebieten der Logik und Informatik auf. Das Halteproblem ist ein eindeutiges kompliziertestes Objekt für die rekursiv aufzâhlbaren Mengen. Das Erfüllbarkeitsproblem SAT ist ein kompliziertestes Objekt in NP. Isomorphie von separaten C*-algebren ist Borel vollständig für Orbit-Âquivalenzrelationen. Dasselbe gilt für Homöomorphismus von kompakten metrischen Räumen. Konjugiertheit von ergodischen Abbildungen des Einheitsintervalles ist Sigma-1-1 vollständig. Der Vortrag gibt einen Überblick über diese Beispiele, und versucht eine Metatheorie zu entwickeln.



Angelegt am Friday, 06.03.2015 12:55 von Julia Osthues
Geändert am Friday, 06.03.2015 12:57 von Julia Osthues
[Edit | Vorlage]

Sonstige Vorträge