Most Tensor Problems Are NP-Hard

被引：833

作者：

Hillar, Christopher J. ^{[1
]}

Lim, Lek-Heng ^{[2
]}

机构：

[1] Math Sci Res Inst, Berkeley, CA 94720 USA

[2] Univ Chicago, Computat & Appl Math Initiat, Dept Stat, Chicago, IL 60637 USA

来源：

JOURNAL OF THE ACM | 2013年 / 60卷 / 06期

基金：

美国国家科学基金会;

关键词：

Algorithms; Theory; Numerical multilinear algebra; tensor rank; tensor eigenvalue; tensor singular value; tensor spectral norm; system of multilinear equations; hyperdeterminants; symmetric tensors; nonnegative definite tensors; bivariate matrix polynomials; NP-hardness; #P-hardness; VNP-hardness; undecidability; polynomial time approximation schemes; UPPER-BOUNDS; COMPLEXITY; APPROXIMATION; EIGENVALUES; SYSTEMS; CUT; DECOMPOSITION; ENTANGLEMENT; ALGORITHMS; NUMBERS;

D O I：

10.1145/2512329

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页数：39

共 131 条

[1] NP-hardness of deciding convexity of quartic polynomials and related problems [J].