PaperlayerView exact revision on arXiv

Source-linked AI summary

Most tensor problems are NP-hard

Christopher Hillar, Lek-Heng Lim

arXiv:0911.1393v5cs.CCmath.NA

TL;DR

The paper asks whether multilinear analogues of efficiently solvable numerical-linear-algebra problems remain tractable. It proves hardness through reductions and complexity analysis, showing broad NP-hardness across tensor decision, approximation, and rank problems, including symmetric cases. The results frame 3-tensor problems as a boundary between tractable linear/convex computation and intractable nonlinear/nonconvex computation.

  • Problem

    Many tensor analogues of standard linear-algebra problems are computable, but known methods become impractical as tensor size grows, motivating complexity analysis of their decisions and approximations.

  • Method

    The paper uses polynomial reductions, including reductions from graph 3-colorability, within a Turing-machine model over rational inputs.

  • Results

    The paper proves NP-hardness for many 3-tensor feasibility, eigenvalue, singular-value, spectral-norm, approximation, and rank problems, and shows symmetric restrictions remain NP-hard.

  • Takeaways & Limitations

    The findings place 3-tensor problems near a computational boundary between tractable linear/convex problems and intractable nonlinear/nonconvex ones.

  • Takeaways & Limitations

    Whether deciding tensor eigenvalue is NP-complete remains open because polynomially verifiable certificate-size bounds are not established.

Abstract

from arXiv · show

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.

1. INTRODUCTION

The paper argues that many natural tensor analogues of efficiently solvable linear-algebra problems are computationally hard, positioning 3-tensor problems near the boundary between tractable linear/convex and intractable nonlinear/nonconvex computation. It establishes NP-hardness across decision, approximation, rank, and symmetric-tensor problems, while identifying limitations and open complexity questions.

  • Motivation: Tensor methods generalize linear-algebra tools used across approximation, biology, graphics, vision, data analysis, and graph theory, but their computational tractability is substantially more limited.The paper contrasts the practical success of matrix routines with the hardness of multilinear analogues.
  • Computational framework: Many naturally occurring problems for 3-tensors are NP-hard under the Turing and Cook–Karp–Levin complexity frameworks.The paper studies rational inputs and YES/NO or rational outputs on a Turing machine.
  • Decision problems: Graph 3-colorability polynomially reduces to tensor 0-eigenvalue over R, making tensor eigenvalue decision NP-hard despite computability over the reals.The same reduction encodes proper 3-colorings as nonzero real solutions of polynomial systems.
  • Scope and open questions: The authors note that NP-hardness is asymptotic, so fixed small tensor dimensions may remain practically manageable, and whether tensor eigenvalue is NP-complete remains open.They also state that rudimentary bounds for polynomially verifiable certificates are out of reach.
  • Approximation and rank: The paper extends hardness to singular-value and spectral-norm decisions, eigenvector and spectral-norm approximation, rank-1 approximation, and tensor rank.It also proves that no PTAS for tensor eigenvectors and no FPTAS for spectral norm exists unless P = NP.
  • Symmetric tensors: Restricting to symmetric tensors does not remove NP-hardness for eigenvalue, singular-value, spectral-norm, or best rank-1 approximation problems.The symmetric spectral-norm result answers an open problem cited by the authors.
  • Counting and rank: Counting real tensor eigenvectors is #P-hard, while tensor rank is NP-hard over both R and C.The paper additionally reports a rational 2×2×2 tensor whose real and rational ranks differ.

2. QUADRATIC FEASIBILITY IS NP-HARD

The paper establishes that quadratic feasibility is NP-hard over the real and complex numbers, via polynomial reductions from graph 3-colorability. It also places this result alongside undecidability over the integers and unresolved decidability over the rationals.

  • Quadratic feasibility is studied as a basic tool for proving hardness results about tensors.The paper introduces quadratic equation solving before applying it to tensor problems.
  • Quadratic feasibility over the integers is undecidable, by encoding Turing-machine halting into systems of quadratic equations.A system has a positive-integer solution exactly when the corresponding machine halts; four-square equations convert positivity constraints into integer equations.
  • Decidability of quadratic feasibility over the rationals remains unknown.The paper contrasts this open rational case with its results over the reals and complexes.
  • Graph 3-colorability is polynomially reducible to quadratic feasibility over both R and C, proving NP-hardness in those fields.The reduction uses a color encoding of 4v homogeneous quadratic polynomials in 2v+1 unknowns.
  • The real-field result follows by transforming complex quadratic systems into homogeneous real systems with twice as many unknowns and equations.A complex solution z=u+iv corresponds to a real solution formed from u and v.
  • The color encoding has a nonzero complex solution exactly when the graph is 3-colorable.Homogeneity and the auxiliary variable allow the encoding to recover a proper coloring from any nontrivial solution.

3. BILINEAR SYSTEM IS NP-HARD

The paper proves that deciding feasibility of tensor bilinear systems is NP-hard over both the real and complex numbers, via reductions from graph 3-colorability. The section also relates bilinear feasibility to hyperdeterminant vanishing while identifying a dimension-condition limitation.

  • Tensor bilinear feasibility: The tensor bilinear feasibility system asks whether nonzero vectors u, v, and w satisfy the tensor-slice bilinear equations.The coefficients are rational tensor entries, and the three vectors must all be nonzero.
  • Hyperdeterminants: For 2 × 2 × 2 tensors, a six-equation bilinear system has a nontrivial solution exactly when the geometric hyperdeterminant vanishes.This parallels the matrix criterion that paired homogeneous linear systems have nontrivial solutions exactly when the determinant is zero.
  • Hyperdeterminants: Hyperdeterminants are defined when l, m, and n satisfy the three dimension inequalities, and their vanishing is equivalent to a nontrivial complex solution of the associated system.These inequalities are the tensor analogue of the dimension requirements for ordinary determinants.
  • Tensor bilinear feasibility: Graph 3-colorability is polynomially reducible to tensor bilinear feasibility, making Problem 3.1 NP-hard over R or C.The construction produces a tensor whose bilinear system has a nonzero complex solution exactly when the graph is properly 3-colored.
  • Limitation: The NP-hardness construction does not satisfy the hyperdeterminant dimension conditions, so NP-hardness of geometric hyperdeterminant vanishing remains open.The paper explicitly identifies this as an unresolved conjecture rather than a consequence of Theorem 3.7.
  • Triple bilinear feasibility: Triple bilinear feasibility, which permits arbitrary coefficient matrices in the three equation families, is also NP-hard over R.An oracle for this problem can support a polynomial-time algorithm for the associated procedure, but the problem itself is NP-hard.

4. COMBINATORIAL HYPERDETERMINANT IS NP-, #P-, AND VNP-HARD

The combinatorial hyperdeterminant is substantially harder than ordinary determinant computation: deciding whether it vanishes is NP-hard, while computing it is also #P-hard and VNP-hard.

  • Definition: For even tensor order d, the combinatorial hyperdeterminant is defined by a formula on n×n×···×n tensors and reduces to the ordinary determinant when d = 2.This notion is distinct from the geometric hyperdeterminant discussed earlier.
  • NP-hardness: Deciding whether det_n(A) = 0 for an integer 4-tensor A is NP-hard.The theorem concerns tensors in Z^n×n×n×n.
  • #P-hardness: The combinatorial hyperdeterminant counts directed Hamiltonian paths in an encoded graph, yielding #P-hardness.The reduction maps a directed graph G to a 4-tensor A_G whose det_n value equals the number of Hamiltonian paths between two vertices.
  • VNP-hardness: The homogeneous polynomial det_n is VNP-hard to compute.The result follows by expressing the permanent in terms of the combinatorial hyperdeterminant.

5. TENSOR EIGENVALUE IS NP-HARD

The paper establishes NP-hardness for tensor eigenvalue problems and even for approximating real eigenvectors. The reductions encode graph 3-colorings using cube roots of unity in tensor eigenvectors.

  • Tensor eigenvalue formulations: Tensor eigenvalues and eigenvectors generalize matrix stationary points of a quadratic Rayleigh quotient to constrained stationary points of a cubic form.Several constraints are considered, including ℓ2- and ℓ3-based formulations.
  • Tensor eigenvalue formulations: The formulations differ in whether their constraint sets are compact, algebraic, or scale-invariant.The paper notes that ℓ2-, ℓ3-, and related constraints trade off these properties differently.
  • Exact eigenvalue decision: Real tensor eigenvalue is NP-hard, with the zero-eigenvalue case reducing to square quadratic feasibility.The same reduction framework also applies to ℓ3-eigenpairs.
  • Approximation hardness: Approximating a real tensor eigenvector within ε = 3/4 is NP-hard.The reduction uses eigenvectors whose coordinates encode cube roots of unity separated enough that such an approximation recovers a graph 3-coloring.

6. TENSOR SINGULAR VALUE AND SPECTRAL NORM ARE NP-HARD

The section establishes NP-hardness for deciding and approximating tensor singular values and vectors, and connects spectral-norm computation to these singular-value problems.

  • Definitions: Tensor singular values generalize matrix stationary-value equations to multilinear forms over product unit ℓp-spheres.The paper considers p = 2 or 3 as natural choices for tensor singular-value definitions.
  • Singular-value decision problems: Deciding whether zero is an ℓ2- or ℓ3-singular value of a tensor is NP-hard over both R and C.For σ = 0, the singular-value definitions coincide with tensor bilinear feasibility under the stated condition.
  • Approximation: Approximating tensor singular vectors over R is NP-hard, and unless P = NP, no PTAS exists for this task.The section states an explicit ε-approximation hardness theorem before deriving the PTAS impossibility result.
  • Singular-value decision problems: Deciding whether any fixed nonzero rational σ is an ℓ2-singular value over R is NP-hard.The reduction constructs tensors from graph instances and uses σ = 1 as the decision threshold.
  • Spectral norm: Tensor spectral-norm questions are NP-hard because the spectral norm is an ℓ2-singular value and the clique reduction tests whether it equals 1.The approximation reduction also recovers the clique number from spectral-norm approximations of the constructed tensors.
  • Reduction from clique: The graph reduction identifies the clique number as the largest index l for which the constructed tensor A_l has singular value 1.For l > ω, the maximum singular value is below 1, while A_ω has singular value 1.

7. BEST RANK-1 TENSOR APPROXIMATION IS NP-HARD

The section formulates best rank-1 approximation through tensor inner products and shows that determining it is NP-hard, while higher-rank best approximations may not exist.

  • Higher-rank approximation: Best rank-r approximation is well-defined only for r = 1 because the set of tensors of rank at most r need not be closed when r > 1.Consequently, the corresponding optimization problem may have no solution.
  • Higher-rank approximation: A rank-3 tensor can have no best rank-2 approximation, illustrating nonexistence of minimizers for higher-rank approximation.The paper notes that this phenomenon occurs across dimensions, orders, ranks, and norms, with certainty for rank-3 tensors in R^2×2×2.
  • Rank-1 approximation: Best rank-1 approximation rewrites a rank-1 tensor as σu ⊗ v ⊗ w with unit-norm factors, reducing the optimization to multilinear evaluation.The inner product satisfies ⟨A, u ⊗ v ⊗ w⟩ = A(u, v, w).
  • Rank-1 approximation: Determining the best rank-1 approximation of a tensor is NP-hard, including when the tensor is restricted to be symmetric of order 3.The paper states the symmetric restriction does not make this problem easier.

8. TENSOR RANK IS NP-HARD

The section extends tensor-rank hardness from finite fields and Q to every field containing Q, including R and C, using encodings of 3SAT formulas.

  • Hardness over Q: Tensor rank over Q is NP-hard because 3SAT formulas can be encoded as rank-threshold questions for rational 3-tensors.Over finite fields, the corresponding decision problem is NP-complete.
  • Field dependence: The reduction addresses the field dependence of tensor rank, since a rational tensor can have strictly lower rank over R than over Q.Thus, hardness over Q does not directly imply hardness over R and C without the extended argument.
  • Extension to R and C: Tensor rank remains NP-hard over every field F containing Q, in particular over R and C.The construction uses only entries −1, 0, and 1 and relies only on field axioms.
  • 3SAT reduction: The 3SAT reduction produces a tensor A whose rank is at most 4n + 2m exactly when the formula with n variables and m clauses is satisfiable.The tensor has dimensions (n+2m+2) × 3n × (3n+m).

9. SYMMETRIC TENSOR EIGENVALUE IS NP-HARD

The section proves that deciding eigenvalues of real symmetric 3-tensors is NP-hard and that approximating their largest ℓ2-eigenvalue admits no FPTAS unless P = NP.

  • Problem setup: The symmetric tensor eigenvalue problem asks whether a specified value is an eigenvalue of a symmetric tensor, extending the eigenvalue question to homogeneous cubic forms.Every homogeneous cubic polynomial corresponds to a symmetric 3-tensor whose maximum eigenvalue is the constrained maximum of the polynomial.
  • Decision hardness: Symmetric tensor eigenvalue over R is NP-hard.The proof relates graph stability numbers to eigenvalue queries for a constructed symmetric tensor.
  • Reduction from graph stability: At most v eigenvalue queries reveal the graph stability number α(G), using candidate values λ_v through λ_1.The first identified eigenvalue in decreasing order gives the maximum relevant value.
  • Input representation: The eigenvalue formulation permits quadratic irrational inputs, represented by rational data and handled using rational arithmetic.The paper explicitly notes this input convention in its discussion of the symmetric eigenvalue decision problem.
  • Approximation hardness: Approximating the largest ℓ2-eigenvalue of a real symmetric tensor has no FPTAS unless P = NP.This follows from the stated inapproximability of the graph stability number.

10. SYMMETRIC SINGULAR VALUE, SPECTRAL NORM, AND RANK-1 APPROXIMATION ARE NP-HARD

The paper extends hardness results to symmetric 3-tensors, showing that singular values, eigenvalues, spectral norm, and best rank-1 approximations remain computationally difficult.

  • The best rank-1 approximation of a symmetric tensor can be chosen to be symmetric, including for symmetric tensors of arbitrary order.
  • Theorem 10.2 establishes NP-hardness over R for deciding the largest ℓ2-singular value or eigenvalue, spectral norm, and best symmetric rank-1 approximation of a symmetric 3-tensor.
  • These three symmetric tensor problems have no FPTAS unless P = NP.
  • The optimal singular value, eigenvalue, spectral norm, and rank-1 approximation value coincide in the symmetric setting.
  • The result answers a prior question about the computational complexity of spectral norm for symmetric tensors.

11. TENSOR NONNEGATIVE DEFINITENESS IS NP-HARD

The section reduces tensor nonnegative-definiteness questions to established matrix cone problems, proving NP-hardness for both nonnegative definiteness and the Gramian property of symmetric 4-tensors. It also derives NP-hardness for quartic sums of fourth powers and eigenvalue-signature determination.

  • Reduction to matrix cones: A symmetric 4-tensor is nonnegative definite exactly when its associated quartic is nonnegative on all vectors.For the constructed tensor, this condition is equivalent to y⊤Ay ≥ 0 for all y ≥ 0, namely copositivity.
  • Reduction to matrix cones: The constructed tensor is Grammian exactly when the underlying symmetric matrix is completely positive.Complete positivity means A = BB⊤ for a matrix B with nonnegative entries.
  • NP-hardness results: Deciding whether a symmetric 4-tensor is nonnegative definite or Grammian is NP-hard.The reductions use copositive and completely positive matrix problems, respectively.
  • Consequences: Deciding whether a quartic is a sum of fourth powers of linear forms is NP-hard.This follows from the Gramian hardness result and the tensor-polynomial correspondence.
  • Eigenvalue characterization: Nonnegative definiteness is equivalent to nonnegativity of all ℓ2- or ℓ4-eigenvalues, so determining the signature of symmetric 4-tensors is NP-hard.The equivalence follows because these eigenvalues are Lagrange multipliers.

12. BIVARIATE MATRIX FUNCTIONS ARE UNDECIDABLE

The section extends matrix-function questions to pairs of matrices viewed as 3-tensors and studies noncommutative bivariate monomials. The resulting bivariate matrix monomial problem is matrix mortality and is undecidable for n > 20.

  • Commuting case: For commuting matrices, bivariate polynomial evaluation uses ordinary monomials A1^i A2^j.The paper defines f(A1, A2) for bivariate polynomials under the commuting assumption.
  • Bivariate matrix functions: A pair of matrices can be represented as a 3-tensor whose two slices are A1 and A2.This representation motivates multilinear analogues of matrix-function problems.
  • Noncommutative case: Without commutativity, evaluating a monomial requires all possible noncommutative products of A1 and A2.The commuting specialization collapses these products to a single ordinary monomial.
  • Undecidability: The bivariate matrix monomial problem asks whether some monic monomial sends the identity matrix to zero.This is the matrix mortality problem for two matrices.
  • Undecidability: For n > 20, deciding whether such a monomial exists is undecidable.The proposition gives the dimension threshold stated in the section.

13. OPEN PROBLEMS

The section identifies unresolved tensor-complexity questions involving hyperdeterminants, symmetric rank, tensor rank, and bilinear optimization. It also notes that NP-hardness is asymptotic and need not preclude useful methods when tensor dimensions are fixed.

  • Hyperdeterminants: The conjectured hyperdeterminant problems include NP-hard decision and approximation tasks, #P-hard magnitude evaluation, and VNP-hard polynomial computation.The conjectures concern inputs over Gaussian rationals or Boolean tensors, with some claims restricted to equal dimensions.
  • Hyperdeterminants: All listed hyperdeterminant hardness statements are conjectured to remain true when l = m = n.This is the symmetric-size specialization stated in the conjectures.
  • Condition numbers: The proposed tensor condition number is expected to be NP-hard to compute, by analogy with the matrix inverse formulation.For matrices, the corresponding optimization has solution A^-1, and the normalized optimum gives the reciprocal condition number.
  • Tensor rank: The paper conjectures that deciding symmetric rank over any extension field of Q is NP-hard.The conjecture concerns whether srankF(S) ≤ r for a symmetric 3-tensor S.
  • Tensor rank: The paper further conjectures that tensor rank and symmetric tensor rank over Q are undecidable.This extends the paper’s stated suspicion that tensor rank is undecidable beyond its established NP-hardness over Q.
  • Bilinear optimization: Bilinear programming feasibility and bilinear least-squares approximation are proposed as additional open complexity problems.The paper distinguishes these from homogeneous bilinear-equation feasibility because all-zero solutions cannot be disregarded in the inhomogeneous formulations.
  • Scope of hardness: NP-hardness is asymptotic, so useful algorithms may still exist when tensor size n is fixed.The paper cites Gröbner-basis computations as a method useful in at least one theorem despite doubly exponential worst-case complexity.

APPENDIX

The appendix gives computational details for a proof of Lemma 8.1, including polynomial constructions and their implication for rational common zeros.

  • Proof details: The proof of Lemma 8.1, which supports Theorem 1.14, uses symbolic computation to obtain the polynomials H1, . . . , H8 and G1, . . . , G8.The stated software is SINGULAR, specifically its lift function; Maple, Mathematica, Macaulay 2, and Sage are also mentioned as alternatives.
  • Polynomial construction: The construction begins with three sets of polynomials and explicitly defines F1, . . . , F8 in terms of variables a_i, b_i, c_i, and d_i.The displayed F-polynomials combine cubic monomials and constants such as −2, 4, and −4.
  • Polynomial construction: The appendix lists explicit polynomial expressions for the G- and H-polynomials used in the proof.The supplied expressions include G2 through G7 and H3 through H7.
  • Consequence: Any rational point making F1, . . . , F8 simultaneously zero must also make both g and h vanish.The appendix notes that expressions such as (41) are far from unique.
Loading 0911.1393v5…