Suchprobleme (2)

Bei COL ist der Suchraum beschränkt: es gibt nur | Farben|| Knoten| verschiedene Färbungen.

Für jede Färbung kann man schnell (polynomiell) prüfen, ob sie Konflikte enthält.

...es gibt aber exponentiell viele Färbungen.


COL gehört zur Komplexitätsklasse NP.

Bedeutung des Namens:

...aber exponentiell breit.

Aufgabe: wie komplex ist 2COL (2 Farben)?



Johannes Waldmann 2006-01-26