This paper studies the algorithmic complexity for computing the Nash equilibrium in the extensively studied Tullock Contest game. The (possibly heterogeneous) elasticity parameter determines whether a contestant 's cost function is convex or concave. Our core conceptual insight is that the domains of governs the complexity for solving Tullock contents. This is illustrated by our following complete set of algorithmic results. - When at most number of contestants have , we show polynomial-time algorithms to determine the existence of a pure Nash equilibrium (PNE), and compute a PNE whenever it exists. Notably, this result is proved under three different regimes, each via quite different techniques: (1) all , (2) all , and (3) a mixed situation with at most number of . - When polynomially many contestants have , we prove that determining the existence of a PNE is NP-complete. In response to this hardness result, we design a Fully Polynomial-Time Approximation Scheme (FPTAS) that finds an -PNE when an exact PNE exists.