A tensor is a generalization of vectors and matrices to higher dimensions and the rank of a tensor also generalizes the rank of a matrix. Namely, the rank of a tensor $T$ is the minimum number of rank one tensors that sum to $T$. A vector and matrix are tensors of degree 1 and 2 respectively.The elements in $T$ come from a field $\mathbb{F}$. If $\mathbb{F}$ is finite, then Hstad proved that deciding if the rank of a degree 3 tensor is at most $r$ is NP-complete, but when $\mathbb{F}$ is an infinite field like the rationals $\mathbb{Q}$, he gives (or cites) no upper bound.Question: What is the best known upper bound for the complexity of deciding if the rank of a degree 3 tensor $T$ over $\mathbb{Q}$ is at most $r$?
Complexity of Tensor Rank over an Infinite Field
ds.algorithms;reference request;computability;tensor rank
The book Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume published this summer (July 2014) largely agrees with the consensus that we reached here.  On page 199, it says:To the best of my knowledge, it is even not known whether [the problem of computing tensor rank] over $\mathbb{Q}$ is decidable. Over $\mathbb{R}$, the situation is somewhat better...The problem is decidable and even in PSPACE, since it can be reduced to the existential theory of the reals.