How high in NP-hard is computing rank of tensors?

114 Views Asked by At

Fix an arbitrary field K. I was reading about the problem of computing rank of tensors and I have a few questions. Can you give an example of a tensor $t\in T:=\otimes_{i=1}^{k}V_{i},$ where each $K$-vector space $V_{i}$ have a finite basis $B_{i}=\{v_{i, j} \mid j\in\{1,\dots,\dim(V_{i})\}$ that generates by tensor multiplication the basis $B_{T}$ of T, such that every pair $t_{l}, t_{m}\in\supp_{B_{T}}(t):=$("the elements of the basis $B_{T}$ over which $t$ is not having null projection") has no k-1 common tensorial factors and verifying $\rank(t)<\card(\supp_{B_{T}}(t)$? And what if every element in the support has the same projection?

In relation with this, I read that tensor rank is NP-complete (finite fields) or NP-hard (rationals). If P=NP could it still happen that computing tensor rank in rationals is P. I mean, is it known if computing tensor rank is definitely and strictly not in NP for any field? Because when I read NP-hard I understand that it is possible still that it is in NP-complete but it is still unkwown. Could you clarify this?

How hard is the tensor rank?
Tensor rank is NP-complete