Klassifizierung von Relationen via berechenbarer Reduktion

Ein wichtiges Ziel der modernen Mathematik ist die Klassifikation von Strukturen und Relationen nach ihrer algorithmischen Komplexität. Häufige Fragen in diese Richtung sind: Wieviel Information ist nötig um gewisse Fragestellungen über eine Struktur zu beantworten? Gegeben zwei Strukturen, welche ist komplizierter als die andere? Berechenbare Strukturtheorie ist ein großes Forschungsfeld welches die formalen Werkzeuge liefert mit denen diese Fragen formuliert werden können. Ein besonders mächtiges Konzept um mathematische Strukturen zu vergleichen sind Reduktionen. Die informelle Idee ist wie folgt. Ein Objekt lässt sich auf ein anderes Objekt reduzieren wenn wir Fragen über Ersteres mit Hilfe von Informationen über das zweite Objekt beantworten können. Zahlreiche verschiedene Formen von Reduktionen wurden untersucht. Sie sind eines der zentralen Forschungsthemen der mathematischen Logik. Der Fokus dieses Projekt ist die Untersuchung von berechenbarer Reduktion, eine wichtige Reduktion welche sehr viel Interesse von Wissenschaftlern in den letzten Jahrzehnten auf sich gezogen hat. Berechenbare Reduktion hat sich als Werkzeug zum Vergleich von der Komplexität einer Klasse von Relationen bewährt die für Mathematiker von zentraler Bedeutung ist, Äquivalenzrelationen. Letztere findet man überall in der Mathematik, sie erfassen den Begriff der Gleichheit zwischen mathematischen Objekten. Das Projekt hat zwei Ziele. Einerseits möchten wir das Konzept der berechenbaren Reduktion von Äquivalenzrelationen auf generelle Klassen von Relationen, wie Graphen, Ordnungen, und andere wichtige Klassen, erweitern. Im Besonderen interessiert uns das Problem ob es in einer gegebenen Klasse Relationen gibt auf die sich alle anderen Relationen reduzieren lassen. Andererseits wollen wir eine generellere Form der berechenbaren Reduktion erforschen bei der die Reduktion nicht algorithmisch sondern nur durch Zuhilfename zusätzlicher Information durchführbar ist. Dadurch erhalten wir ein Werkzeug welches es uns erlaubt alle Möglichkeiten wie sich eine Reduktion zwischen zwei Strukturen definieren lässt zu untersuchen. Zusammenfassend wollen wir mit diesem Projekt das volle Potential eines Werkzeuges entfachen dessen Eignung als Klassifikationswerkzeug bekannt ist, allerdings nur in einer eingeschränkten Version.

Equivalence relations capture the notion of similarity. They are a major object of study in logic and computer science. In this project, we explored a powerful classification tool for measuring the complexity of equivalence relations: computable reducibility. We used such a tool for achieving many goals, including the classification of equivalence relations which are computable up to finitely many mistakes, the study of word problems in algebra, and for calculating how much information is needed to perform reductions between given equivalence relations. Within the project we also addressed two other focuses that have sprung up naturally from working around the project goals. First, we analyzed many algorithmic properties of a natural way of relaxing isomorphism: the bi-embeddability relation. Secondly, we contributed to algorithmic learning theory, a long-standing research program which deals with the question of how a learner, provided with more and more data about some environment, is eventually able to achieve systematic knowledge about it. Borrowing ideas from computable structure theory, we developed a novel framework for formalizing the notion of learning an algebraic structure in the limit. Using infinitary logic, we were able to obtain a syntactic characterization of which families of structures are learnable, according to this framework. The scientific outputs of the project include 16 articles and 20 talks and seminars.