Suchprobleme (2)

Bei COL und LL sind die Suchräume beschränkt: es gibt nur $\vert\textrm{Knoten}\vert^{\vert\textrm{Farben}\vert}$ verschiedene Färbungen, bzw. nur $\vert\textrm{Spielfelder}\vert^{\vert\textrm{Roboter}\vert}$ verschiedene Anordnungen. Schlimmstenfalls probiert man alles durch.

Der Unterschied ist jedoch, daß man für eine Färbung sehr schnell (in polynomieller Zeit) prüfen kann, ob sie eine Lösung ist;

aber eine Anordnung von Robotern allein noch keine Lösung ist; man muß alle Folgen untersuchen. Da nur wiederholungsfreie Folgen interessant sind, sind es trotzdem nur endlich viele.