- 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)
Johannes Waldmann
2008-01-24