Autoreduktionen zufaelliger Mengen

heisst zufaellig bezueglich einer gegebenen Klasse von
Wettstrategien, falls beim sukzessiven Wetten auf die jeweils
naechste Stelle der Menge der Gewinn beschraenkt bleibt. Als
Spezialfaelle dieser Definition erhaelt man die Klassen der
p-zufaelligen, der rek-zufalligen und der Martin-Loef-zufaelligen
Mengen indem man die betrachteten Wettstrategien einschraenkt auf in
polynomieller Zeit berechenbare, auf totale berechenbare, bzw. auf in
geeigneter Weise effektiv approximierbare.

Der Vortrag behandelt die Frage inwieweit sich Stellen einer
zufaelligen Menge aus den restlichen Stellen berechnen lassen.
Formal heisst (bezueglich einer gegebenen Klasse von Reduktionen)
eine Menge A autoreduzierbar auf einer Menge E, falls es eine
Reduktion gibt, welche fuer alle x entweder A(x) oder den Wert "?"
ausgibt ohne das Orakel an der Stelle x zu befragen, wobei fuer alle
x in E tatsaechlich A(x) ausgegeben wird.

Es laesst sich leicht zeigen, dass eine rek-zufaellige Mengen auf
einer unendlichen berechenbaren Menge nicht
truth-table-autoreduzierbar sein kann (d.h., autoreduzierbar vermoege
einer totalen berechenbaren Reduktion). Andererseits erhaelt man das
etwas ueberaschende Ergebnis, dass jede p-zufaellige Menge (und damit
insbesondere auch jede rek-zufaellige und jede Martin-Loef-zufaellige
Menge) in polynomieller Zeit autoreduzierbar auf einer unendlichen
Menge ist.

Man kann sich nun weiter fragen, wie dicht bei einer Autoreduktion
einer zufaelligen Menge A die Stellen x liegen koennen, an denen A(x)
tatsaechlich berechnet wird.
Formal heisst eine Menge A autoreduzierbar mit Dichte a(n) falls A
autoreduzierbar ist auf einer Menge E, welche fuer alle n mindestens
einen Anteil von a(n) der ersten n Stellen enthaelt. Beispielsweise
ist eine Menge autoreduzierbar mit Dichte 1/2 falls mindestens jede
zweite Stelle von A berechnet wird. Fuer rek-zufaellige Mengen lassen
sich die erreichbaren Dichten gut charakterisieren. Rek-zufaellige
Mengen sind nie truth-table-autoreduzierbar mit konstanter Dichte
a(n)>0, aber fuer jede berechenbare nichtfallende und unbeschraenkte
Funktion b ist jede rek-zufaellige Menge truth-table-autoreduzierbar
mit Dicht a(n)=1/b(n).

Bei der Konstruktion von Autoreduktionen zufaelliger Mengen wird die
Loesung des Hutproblems verwendet. Dieses wurde von Ebert und Vollmer
urspruenglich zur Illustration der verwendeten Methoden eingefuehrt,
hat aber inzwischen auch ausserhalb der theoretischen Informatik
Beachtung gefunden (siehe New York Times vom 10. April 2001 und ZEIT
vom 3. Mai 2001).
Beim Hutproblem wird jedem der n Mitspielern durch Muenzwurf ein
roter oder blauer Hut zugeteilt. Die Spieler sehen -- aehnlich wie
bei einer Autoreduktion -- jeweils nur die Huete der anderen Spieler.
Jeder Spieler kann einen Tipp bezueglich der Farbe seines Hutes
abgeben, das Spiel ist gewonnen, wenn mindestens einer richtig und
keiner falsch geraten hat. Die Mitspieler koennen vor dem Spiel eine
gemeinsame Strategie festlegen, waehrend des Spiels haben sie aber
keinerlei Moeglichkeit sich zu verstaendigen und es ist ihnen auch
nicht bekannt, ob und wie die anderen antworten. Erstaunlicherweise
gibt es fuer alle n der Form 2^l-1 eine Strategie, bei welcher das
Spiel mit Wahrscheinlichkeit 1-1/(n+1) gewonnen wird.