Klaus-Jörn Lange (Uni Tübingen): Eine algebraische Charakterisierung der Klasse TC0

Klassen im unteren Komplexitätsbereich werden üblicherweise durch Schaltkreise und durch Prädikatenlogik definiert. Eine zunehmende Bedeutung gewannen algebraische Charakterisierungen. Die durch Mehrheitsquantoren beziehungsweise -gatter erklärte Komplexitätsklasse TC0 entzog sich allerdings bislang diesem Ansatz. Diese Lücke konnte durch die Einführung der endlich getypten (aber unendlichen) Monoide und Gruppen geschlossen werden. In dem Vortrag werden zwei Klassen endlich getypter Gruppen vorgestellt, die genau TC0 in zwei verschiedenen Uniformitätsausprägungen darstellen.