50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Ressourcen-Beschränkte Hausdorff-Dimension


Ressourcen-Beschränkte Hausdorff-Dimension

Frank Stephan, Heidelberg


Eine Teilklasse  des Cantorraums 0,1 hat genau dann Lebesgue-Maß, wenn es eine Wettstrategie gibt , welche auf jeder Menge in dieser Klasse gewinnt. Dabei setzt  für 0,1,2, . . . bei Kenntnis von . . .  eine gewisse Menge seines Kapitals (ggf. auch ) auf einen Wert 0,1 und erhält das eingesetzte Kapital doppelt zurück, wenn  ist, und verliert es, sonst. Die Strategie  ist auf  erfolgreich, wenn das Kapital von  bei jeder Menge  im Limes unendlich wird.

Ausgehend von diesem Resultat von Ville wurden von Schnorr und Lutz effektive Maßbegriffe eingeführt, indem sie nur berechenbare Wettstrategien  zulassen. Lutz ging einen Schritt weiter und fordert, dass . . .  in Zeit polynomial in  (nicht: polynomial in ) berechnet wird. Ausserdem beschränkt man sich auf Teilklassen  der in exponentieller Zeit berechenbaren Mengen  wo es zu  ein  gibt, so dass jeder Wert  in Zeit  berechnet wird.

Neben dem bereits erwähnte Lebeguemaß läßt sich auch der Begriff der Hausdorff-Dimension  in dieses Szenario übertragen: eine Klasse  hat genau dann Hausdorff-Dimension  wenn das Infimum aller  ist so dass  für alle  für unendlich viele  mindestens das Kapital  angesammelt hat. Der Vortrag gibt die verschiedenen Charakterisierungen der Klassen mit Hausdorff-Dimension  sowie  wieder und stellt einige grundlegenden Ergebnisse vor.