My understanding is that the number of colors is just the maximum number of live values at any point, which is easy to determine, so the theoretically NP-complete part of graph-coloring is solved before you even start trying to pick registers. After that, it gets tricky to even define optimality, because you have to trade off the likely runtime costs of different sets of moves (which in my mind includes which variables to spill to the stack when). If there's a formal framework that decisively handles that stuff, someone please let me know.
OTOH, GP only actually said "NP problem", of which P is a subset, so they're not wrong. :)