Registervergabe

• Werte von lokalen Variablen in Blöcken und von (Teil-)Ausdrücken sollten, wenn möglich, in Prozessor-Registern stehen, (Zugriff ist sehr viel schneller aus auf Hauptspeicher).
• gleichzeitig benötigte Werte müssen in verschiedenen Registern stehen (definiert Graph)
• Registerzahl der CPU ist begrenzt (Anzahl der Farben)

Problem COL= {(G, k) : Graph G besitzt konfliktfreie Färbung mit k Farben }.

...3COL ist NP-vollständig (Reduktion von 3SAT)