Håstad, Johan Tensor rank is NP-complete. (English) Zbl 0716.65043 J. Algorithms 11, No. 4, 644-654 (1990). 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 Cited in 1 ReviewCited in 59 Documents MSC: 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 Keywords:tensor rank; NP-complete problems; NP-hard problems; finite field PDF BibTeX XML Cite \textit{J. Håstad}, J. Algorithms 11, No. 4, 644--654 (1990; Zbl 0716.65043) Full Text: DOI