  We prove that multilinear (tensor) analogues of many efficiently computable
problems in numerical linear algebra are NP-hard. Our list here 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 of a 4-tensor is NP-, #P-, and VNP-hard. We
shall argue that our results provide another view of the boundary separating
the computational tractability of linear/convex problems from the
intractability of nonlinear/nonconvex ones.
