Als ich ein Kind war, kauften mir meine Eltern einmal ein Lexikon zu Weihnachten. Ich dachte, das sei das beste Geschenk aller Zeiten, denn endlich war ich in der Lage, alles, was man wissen konnte, aus einem einzigen Buch zu lernen. Ich fing also sofort an zu lesen, aber ich muss zugeben, dass ich schnell wieder aufgab.
Das lag daran, dass die Beschreibung im ersten Eintrag unter dem Buchstaben A mich aufforderte, zu einer anderen Seite zu springen. Nehmen wir zum Beispiel an, Sie schlagen das Wort «Lexikon» nach. Seine Definition lautet: «Ein Buch, das alle Wörter einer Sprache auflistet». Also schlagen Sie das Wort «Buch» und seine definierenden Begriffe nach, dann das Wort «Liste» und seine definierenden Begriffe, und immer so weiter.
Gefangen in einer Schlaufe
Aber jetzt kommt die Krux: Da es eine endliche Anzahl von Wörtern gibt, stiess ich offensichtlich auf ein Wort, das ich bereits gelesen hatte. Darum war ich für immer in einer Schlaufe im Lexikon gefangen. Oder, mit anderen Worten, ich war wieder da, wo ich angefangen hatte, aber ohne das ganze Buch gelesen zu haben! Das brachte mich ins Grübeln: Wie viele solcher Kreisprozesse gab es in dem Buch? Und wie gross waren sie?
Vom Standpunkt der Informationstechnologie betrachtet ist das in der Tat ein interessantes Problem . Stellen Sie sich vor, Sie haben eine Reihe von Objekten und eine Reihe von Verbindungen zwischen diesen Objekten; zum Beispiel könnten die Objekte Städte sein und die Verbindung eine Strasse, die zwei Städte verbindet. Oder, wie in unserem Lexikon, die Objekte sind Wörter, und die Verbindungen sind die zwischen dem Lexikoneintrag und all den anderen in seiner Definition verwendeten Wörter. Informatiker nennen solch eine Anordnung von Objekten einen «Graphen», und unser Problem besteht folglich darin, eine Kreisbahn in einem solchen Graphen zu finden.
Wikipdia statt Lexikon
In einem echten Lexikon ist die Suche anstrengend, da Sie viele Seiten umblättern müssen. Aber in einem Onlinelexikon wie Wikipedia können Sie einen Algorithmus schreiben, der den Links und den ihr folgenden Beschreibungen automatisch folgt, um zu prüfen, ob ein Kreis vorliegt.
Es gibt viele Methoden, an einem Computer einen Algorithmus zu programmieren, der einen Kreis finden kann; und obwohl Sie dabei effizienter oder weniger effizient sein können, ist es ein Leichtes, die Länge des kürzesten Kreises zu messen. Aber angenommen, ich möchte herausfinden, ob ich die ganze Wikipedia in einem grossen Kreis lesen kann, ohne in einer kurzen Schlaufe gefangen zu werden, wie an jenem schicksalhaften Weihnachtstag. Wie sich herausstellt, ist das ein Problem aus einer anderen Liga!
Ein Kreis, der alle Objekte in einem Graphen nur einmal berührt, heisst Hamiltonkreis. Zu bestimmen, ob ein Hamiltonkreis existiert oder nicht, ist eines der schwierigsten Probleme in der Informatik, für das keine brauchbare Lösung bekannt ist. Die einzige Möglichkeit bestände darin, alle Kreise einzeln zu untersuchen; aber wenn Sie zählen würden, wie viele Kreise es in der Wikipedia gibt, kämen Sie auf eine Zahl, die grösser ist als die Anzahl Teilchen im Universum.
