Komplexität der Geographie

Das allgemein als Prototyp eines PSPACE-vollständigen Spiels gesehene Geographiespiel wird bezüglich seiner Komplexität genauer untersucht. Das Interesse der theoretischen Informatik an diesem Spiel wurde sehr durch die Darstellung in dem Lehrbuch von Papadimitriou [Pap94] gefördert. Allerdings bestimmt dieses Lehrbuch nicht die Komplexität des Standardspiels sondern verwendet eine Verallgemeinerung. Die Aussage in dem Lehrbuch bleibt damit etwas unbefriedigend und hinter den Möglichkeiten. Wir zeigen hier, dass die komplexitätstheoretische Charakterisierung schon für die Standardvariante des Spiels gilt.

In der konkreten Version, die man tatsächlich als Gesellschaftsspiel verwenden kann, gibt es unserem Alphabet entsprechend nur 26 Buchstaben. Es ergibt sich, dass man bei konstanter Buchstabenzahl optimale Spielstrategien in polynomieller Zeit berechnen kann.

In der Praxis muss man allerdings wiederum anders vorgehen, um verwertbare Ergebnisse zu erhalten. Wir beschreiben das anhand eines Spiels mit den 305 Millionenstädten dieser Welt.