[Register Allocation Theory] Is register allocation indeterminate?

Has anyone read anything about register allocation being
indeterminate? I have seen much literature about "optimal register
allocation," but does anyone know a case where it is not?

Thanks,
Jeff Kunkel