  We show that determining the rank of a tensor over a field has the same
complexity as deciding the existential theory of that field. This implies
earlier NP-hardness results by H{\aa}stad~\cite{H90}. The hardness proof also
implies an algebraic universality result.
