Most Tensor Problems Are NP-Hard

We prove that multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NP-hard. Our list includes: determining the feasibility of a system of bilinear equations, deciding whether a 3-tensor possesses a given eigenvalue, singular value, or spectral norm; approximating an eigenvalue, eigenvector, singular vector, or the spectral norm; and determining the rank or best rank-1 approximation of a 3-tensor. Furthermore, we show that restricting these problems to symmetric tensors does not alleviate their NP-hardness. We also explain how deciding nonnegative definiteness of a symmetric 4-tensor is NP-hard and how computing the combinatorial hyperdeterminant is NP-, #P-,…

• NS
  National Science Foundation
• DO
  Division of Mathematical Sciences

  Awards: DMS 1209136, DMS-1057064, DMS-0441170
• AF
  Air Force Office of Scientific Research

  Award: FA9550-13-1-0133