[thechao]

If you're willing to work in the SSA domain, and not do any spill/fill, you can do optimal RA in polynomial time. (Usually quoted as linear, but quadraticish IRL.)