Phasenübergänge in polynomialen Problemen

Die algorithmische Komplexität eines Problems hängt von der komkreten Instanz des Problems ab. In der klassischen Komplexitätstheorie untersucht man deshalb fast ausschließlich worst-case Instanzen. Die liefern eine obere Schranke für die Laufzeit von Algorithmen und erlauben es, eine mächtige Theorie zu konstruieren. Allerdings korrespondieren ihre Ergebnisse nicht immer mit der Komplexität von Problemen, die typischerweise z.B. in Anwendungen vorkommen. Hier hat sich als Alternative die Analyse der Komplexität von Zufallsinstanzen etabliert. Dabei stellt sich heraus, das die zu erwartende Komplexität empfindlich von den Parametern des Zufallsensembles abhängen kann. In der Physik spricht man von einem Phasenübergang, und dieser Begriff hat sich inzwischen auch in der Informatik eingebürgert.

Bisher wurden Phasenübergänge fast ausschließlich in Problemen gefunden und analysiert, deren worst-case Komplexität NP-vollständig ist. In diesem Projekt werden nun Phasenüregänge untersucht, die in Problemen mit polynomialer worst-case Komplexität auftauchen. Ein erstes Beispiel ist das Circuit-Value-Problem (CVP), dessen worst-case Komplexität P-complete ist, d.h.
das nicht effizient parallelisierbar ist.