Textprobe: Kapitel 4.1: Problemstellung in diesem Abschnitt interessieren wir uns für Algorithmen, um Zählprobleme zu lösen. Um einige generelle Techniken zu zeigen, sollten wir uns noch mal dem Beispiel mit den möglichen q-Färbungen eines Graphen aus dem letzten Abschnitt zu wenden. Insbesondere werden wir sehen, wie sich die MCMC-Technik als nützlich in diesem Kontext erweist. Wenn man naiv an das Problem herangehen würde, könnte man glauben, das Problemlösen zu können, indem man einfach alle möglichen Konfigurationen, also Elemente von {1,...,q} V, in lexikographischer Reihenfolge durch geht und dann alle davon zählt, bei denen es sich um zulässige Konfigurationen handelt. Leider handelt es sich hierbei um einen sehr zeitaufwendigen Algorithmus, denn die Elemente von {1,...,q} V wachsen exponentiell mit der Mächtigkeit von V an. Insbesondere sind wir deshalb hier interessiert, Algorithmen zu finden, die eine polynomiale Laufzeit besitzen. Das bedeutet, dass ein Polynom p (k) in der Größe k des Problems existiert, sodass die Laufzeit begrenzt ist durch p (k), für jede Instanz des Problems der Größe k. Das ist dasselbe, wie nach Algorithmen zu fragen, deren Laufzeit durch Ck? begrenzt ist, für irgendwelche Konstanten C und ?. In vielen Fällen können wir aber noch nicht einmal das erreichen und müssen uns mit Algorithmen zufriedengeben, die die Mächtigkeit der Menge aproximieren, d.h. deren Ausgabe sich irgendwo zwischen (1??)N und (1+?) N befindet, wenn N die wahre Mächtigkeit der Menge ist. Die Fehlertoleranz ? erhält der Algorithmus als Eingabe, sodass der Fehler beliebig klein werden kann, wenn man dadurch eine größere Laufzeit in kauf nimmt, die aber immer durch ein Polynom p? (k) in der Größe des Problems begrenzt ist. Leider können wir in vielen Fällen aber noch nicht einmal sicherstellen, dass sich das Ergebnis des Algorithmus immer innerhalb der vorgegbenen Fehlerschranken bewegt, sondern dies nur mit einer Wahrscheinlichkeit von 23 der Fall ist. Das bedeutet, dass wenn wir dem Algorithmus ? als Eingabe geben, dieser folgende Eigenschaften besitzt: 1. Mit einer Wahrscheinlichkeit von mindestens 23, gibt der Algorithmus eine Antwort im Bereich (1??) N und (1+?) N aus, wobei N die wahre Antwort des Zählproblems darstellt. 2. Für jedes ?>0 existiert ein Polynom p?(k) in der Größe k des Problems, sodass für jedes Auftreten des Problems der Größe k der Algorithmus in höchstens p?(k) Schritten terminiert. Ein solcher Algorithmus heißt zufälliges Polynom-Zeit Approximations-Schema. Dieser Abschnittbeschäftigt sich mit der Konstruktion eines solchen Schemas für die q-Färbungen von Graphen.