The paper "Most Tensor Problems are NP-Hard" by Christopher J. Hillar and Lek-Heng Lim explores the computational complexity of various problems in numerical multilinear algebra, specifically focusing on 3-tensors. The authors prove that many efficiently computable problems in linear algebra have NP-hard analogues in multilinear algebra. These problems include determining the feasibility of a system of bilinear equations, deciding the existence of a given eigenvalue, singular value, or spectral norm for a 3-tensor, approximating these values, and determining the rank or best rank-1 approximation of a 3-tensor. They also show that these problems remain NP-hard even when restricted to symmetric tensors. Additionally, they demonstrate that deciding the nonnegative definiteness of a symmetric 4-tensor and computing the combinatorial hyperdeterminant of a 4-tensor are NP-, #P-, and VNP-hard, respectively. The paper provides a framework for understanding the computational boundaries between tractable linear/convex problems and intractable nonlinear/nonconvex ones, highlighting the computational hardness of tensor problems.The paper "Most Tensor Problems are NP-Hard" by Christopher J. Hillar and Lek-Heng Lim explores the computational complexity of various problems in numerical multilinear algebra, specifically focusing on 3-tensors. The authors prove that many efficiently computable problems in linear algebra have NP-hard analogues in multilinear algebra. These problems include determining the feasibility of a system of bilinear equations, deciding the existence of a given eigenvalue, singular value, or spectral norm for a 3-tensor, approximating these values, and determining the rank or best rank-1 approximation of a 3-tensor. They also show that these problems remain NP-hard even when restricted to symmetric tensors. Additionally, they demonstrate that deciding the nonnegative definiteness of a symmetric 4-tensor and computing the combinatorial hyperdeterminant of a 4-tensor are NP-, #P-, and VNP-hard, respectively. The paper provides a framework for understanding the computational boundaries between tractable linear/convex problems and intractable nonlinear/nonconvex ones, highlighting the computational hardness of tensor problems.