Yeah, the number of "registers" needed isn't really NP-complete the way that the number of colors in a graph is. It's just the maximum number of live values, which, while not exactly trivial, is not that hard to figure out.