Tensor rank is NP-complete. (English) Zbl 0716.65043

The author proves that computing the rank of a three-dimensional tensor over a finite field is NP-complete and over the rational numbers the problem is NP-hard.
Reviewer: H.Hollatz


65F30 Other matrix algorithms (MSC2010)
65Y20 Complexity and performance of numerical algorithms
15A72 Vector and tensor algebra, theory of invariants
03D15 Complexity of computation (including implicit computational complexity)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI