We present a full description of the algorithmic complexity of computing the tensor rank. Namely, computing the rank of a tensor with respect to an integral domain is polynomial time equivalent to solving a system of polynomial equations over that domain. In particular, computing the rank of a tensor over the integers is an undecidable problem. Our proof uses a reduction from the minimal rank matrix completion problem, and if time allows, we will present a related technique that lead to counterexamples to Strassen's direct sum and Comon's conjectures.