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

Håstad, Johan

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

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