The work establishes a fundamental tradeoff between rate, reliability and computational complexity, for the general setting of outage-limited MIMO communications. In the high-SNR regime, the tradeoff is optimized over all encoders, all decoders, and all policies. By policies, we mean to describe a set of complexity-regulating rules that may reduce the number of flops by trading off error performance for encoder-decoder computational complexity. The work then proceeds to explicitly identify encoder-decoder designs and policies, that meet this optimal tradeoff for all channel dimensions, for different communication scenarios, as well as for most fading statistics. The encoders are based on cyclic-division algebra lattice designs, the decoders on lattice-reduction aided regularized linear detection, and the policies are based on flop bounds on the computational complexity of the LLL algorithm. In practice, this tradeoff aims to meaningfully quantify different pertinent and interrelated limits, such as the optimal rate-reliability capabilities per unit complexity and power, the optimal diversity gains per complexity costs, or the optimal goodput per flop. Finally the tradeoff's simple nature, renders it useful for insightful comparison of the rate-reliability-complexity capabilities for different encoders-decoders.