Complexity of Tensor Rank over an Infinite Field 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 Håstad 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$?
There is a recent preprint about this: http://galton.uchicago.edu/~lekheng/work/np.pdf . It shows that most rank-related issues with tensors are NP hard over $\mathbb{R}$ and $\mathbb{C}$. (It also mentions that deciding the rank over $\mathbb{Q}$ is NP hard.)