Most Tensor Problems Are NP-Hard

• Autor: Hillar, Christopher J ; Lim, Lek-Heng
• Materias: Algorithmics. Computability. Computer arithmetics ; Algorithms ; Applied sciences ; Approximation ; bivariate matrix polynomials ; Computer science; control theory; systems ; Eigen values ; Exact sciences and technology ; hyperdeterminants ; Linear algebra ; Linear equations ; Mathematical problems ; nonnegative definite tensors ; NP-hardness ; Numerical analysis ; Numerical multilinear algebra ; P-hardness ; polynomial time approximation schemes ; Studies ; symmetric tensors ; system of multilinear equations ; tensor eigenvalue ; tensor rank ; tensor singular value ; tensor spectral norm ; Theoretical computing ; undecidability ; VNP-hardness
• Es parte de: Journal of the ACM, 2013-11, Vol.60 (6), p.1-39
• Notas: ObjectType-Article-2
  SourceType-Scholarly Journals-1
  ObjectType-Feature-1
  content type line 23
  
• Descripción: 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-, and VNP-hard.
  
• Editor: New York, NY: ACM
  
• Idioma: Inglés