Algorithmische Zufälligkeit und berechenbare Modelltheorie

Eine zentrale Frage der berechenbaren Modelltheorie ist, welche algorithmische Komplexität verschiedene Repräsentationen einer algebraischen Struktur haben. Die Menge dieser Komplexitäten heißt das Grad-Spektrum der Struktur. Für viele Strukturen, mit verschiedensten computationalen und modelltheoretischen Eigenschaften, wurden die Grad-Spektra bereits ausführlich untersucht. Im Zusammenhang damit steht die Frage, welche Komplexität eine zusätzliche Relation auf einer berechenbaren Struktur hat. Der Begriff des Grad-Spektrums einer Relation charakterisiert den Unterschied der algorithmischen Eigenschaften der verschiedenen berechenbaren Repräsentationen derselben algebraischen Struktur. Es gibt interessante Verbindungen zwischen zwei Arten von Spektren. Ein anderes wichtiges Teilgebiet der Berechenbarkeitstheorie ist algorithmische Zufälligkeit. Die Hauptfrage ist: Was heißt es, dass eine Menge natürlicher Zahlen (oder äquivalent: eine reelle Zahl) zufällig ist, und wie hängt dieser Begriff mit der computationalen Komplexität der Menge zusammen? Verschiedene Klassen reeller Zahlen wurden in dieser Hinsicht untersucht (z.B. Grade, die eine Martin-Löf Zahl enthalten, DNC oder PA Grade). Das eingereichte Projekt verbindet Fragen aus berechenbaren Modelltheorie und aus algorithmischer Zufälligkeit. Wir fragen ob es eine Struktur gibt, deren Grad-Spektrum aus genau den DNC Graden oder aus genau den PA Graden besteht; und analog dazu ob es eine Relation auf einer berechenbaren Struktur mit einem solchen Grad-Spektrum gibt. Außerdem, zielen wir eine Charakterisierung von n-Zufälligkeit und n-Generizität mittels Strukturen zu finden. Das Projekt wird also einerseits neue Beispiele von algebraischen Strukturen mit interessanten computationalen Eigenschaften liefern; andererseits wird es neue Charakterisierungen von Grad- Klassen liefern, die in dem Gebiet der algorithmische Zufälligkeit von Bedeutung sind.

Das Projekt befasst sich mit zwei Themen. Der Hauptschwerpunkt war, die Interaktion zwischen Zufälligkeit und Berechenbarkeit zu erforschen. Mit Koautoren, haben wir das seit langer Zeit bestehende Covering Problem für Martin-Löf-Zufälligkeit gelöst, indem wir die Interaktion zwischen Zufälligkeit und Analysis untersucht haben. Wir haben auch eine Reihe damit zusammenhängender Ergebnisse erhalten. Wir haben auch totale Ordnungen, Äquivalenzrelationen und eine effektive Version des Auswahlaxioms untersucht. Im Bereich totaler Ordnungen gibt es ein altes Resultat von Watnik und Ash für abzählbare totale Ordnungen. Mit Koautoren haben wir eine Verallgemeinerung auf größere totale Ordnungen gefunden und bewiesen. Für Äquivalenzrelationen haben wir die Relation der hyperarithmetischen Isomorphie berechenbarer Strukturen erforscht. Mit Koauthoren haben wir gezeigt, dass diese Relation Pi-1-1 vollständig ist. Das ist das erste natürliche Beispiel einer vollständigen Relation für diesen Level. Die Version des Auswahlaxioms, die wir untersucht haben, heißt das Finite Intersection Prinzip und behauptet die Existenz bestimmter Familien von sich überlappenden Mengen. Das Prinzip stellt fest, dass solche Familien immer existieren. Mit Koautoren haben wir die Komplexität eines Algorithmus untersucht, der so eine Familie findet. Wir haben gezeigt, dass unter bestimmten Bedingungen so eine Familie genau so schwierig zu finden ist wie ein 1-Generic. Aufbauend auf unserer Arbeit ist dieses Ergebnis später von anderen verallgemeinert worden. Das zweite Thema war parametrische Komplexitätstheorie. Diese bietet einen Rahmen fuer eine feinere Analyse der Berechnungskomplexität von Problemen. Probleminstanzen haben einen assoziierten Parameter, eine natürliche Zahl, und algorithmische Resourcen werden gemessen als zweistellige Funktionen der Länge und des Parameters einer Instanz. Parameterische Zeit- und Platzkomplexität sind etablierte Forschungsgebiete. Wir haben die theoretischen Grundlagen für eine parametrische Analyse von Zufallskomplexität gelegt und parameterische Analoga verschiedener klassischer Resultate bewiesen. Wir haben eine neue Art und Weise dafür vorgeschlagen, Parametrisierungen zur Untersuchung der Komplexität von Beweissystemen heranzuziehen. Wir haben natürliche parameterisierte Versionen der wichtigsten starken aussagenlogischen Beweiskalküle definiert und deren relative Stärke bezüglich einem neu von uns eingeführten Simulationsbegriff untersucht. Außerdem haben wir die Frage untersucht, inwieweit es möglich ist, in effizienter Weise Probleminstanzen zu produzieren, die hart für einen gegebenen Algorithmus oder ein gegebenes Beweissystem sind. Wir erhielten einige positive und einige negative Resultate. Wir haben ein modelltheoretisches Präservationstheorem für sogenannte quantifizierte Constraint Satisfaction Probleme über gewissen unendlichen Datenbanken bewiesen. Dies ist unverzichtbar für einen algebraischen Ansatz zur Komplexitätstheorie von Constraint Satisfaction Problemen, der sich im unquantifizierten Fall als sehr erfolgreich herausgestellt hat.