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:

• N: es ist ein Suchproblem
• P: der Suchbaum ist nur polynomiell tief ...

...aber exponentiell breit.

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