×

zbMATH — the first resource for mathematics

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

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
PDF BibTeX XML Cite
Full Text: DOI