Algorithmische Zufälligkeit in der Berechnbarkeits- und Komplexitätstheorie

• Antragsteller: Privatdozent Dr. Wolfgang Merkle
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2012
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 33485683

Das Thema des Projekts Computable Randomness and Dimension (Cordi) ist algorithmische Zufälligkeit. Unendliche Binärfolgen, kurz Folgen, die algorithmisch zufällig sind, haben interessante berechenbarkeits- bzw. komplexitätstheoretische Eigenschaften und werden seit einigen Jahren verstärkt untersucht. Die algorithmische Zufälligkeit einer Folge kann auf verschiedene, teilweise äquivalente Weisen charakterisiert werden; im Rahmen eines gegebenen Berechnungsmodells unter anderem dadurch, wie stark die Folge komprimiert werden kann oder dadurch, wie erfolgreich Wettstrategien beim Wetten auf die Bits der Folge sein können. Im ersten von zwei sich überschneidenden Teilprojekten des Projekts Cordi werden Zusammenhänge zwischen dem Grad der algorithmischen Zufälligkeit und anderen berechenbarkeits- und komplexitätstheoretischen Eigenschaften von Folgen untersucht, unter anderem sollen hier neuere Ergebnisse aus der Berechenbarkeitstheorie über den Zusammenhang von Komprimierbarkeit und effektiv nutzbarem Informationsgehalt einer Folge erweitert und auf den ressourcenbeschränkten Fall übertragen werden. Das zweite Teilprojekt behandelt Zusammenhänge zwischen algorithmischer Zufälligkeit und anderen Zufälligkeitsbegriffen, wie sie etwa in der Kryptographie oder bei der Derandomisierung probabilistischer Algorithmen verwendet werden. Dabei werden grundlegende Fragen zu den Beziehungen zwischen den verschiedenen Zufälligkeitsbegriffen untersucht, sowie Anwendungen der zu den verschiedenen Zufälligkeitsbegriffen gehörigen Ergebnissen und Methoden auf Fragestellungen im Zusammenhang mit den jeweils anderen Begriffen.

• DFG-Verfahren: Sachbeihilfen