Abstract: We show that determining the rank of a tensor over a field has the same complexity as deciding the existential theory of that field. This implies earlier NP-hardness results by H{aa}stad~cite{H90}. The hardness proof also implies an algebraic universality result.
Recommendations
- On the complexity of finding tensor ranks
- Tensor rank is NP-complete
- Tensor rank is hard to approximate
- Publication:5011283
- Bounds on the tensor rank
- Geometric complexity theory and tensor rank
- An upper bound for the tensor rank
- Tensor decompositions and rank increment conjecture
- Tensor decompositions in rank \(+1\)
- Rank properties and computational methods for orthogonal tensor decompositions
Cites work
- scientific article; zbMATH DE number 4092241 (Why is no real title available?)
- scientific article; zbMATH DE number 17663 (Why is no real title available?)
- Bounds for rectilinear crossing numbers
- Characterizing integers among rational numbers with a universal-existential formula
- Complexity of some geometric and topological problems
- Global properties of tensor rank
- Hilbert's Nullstellensatz is in the polynomial hierarchy
- Intersection graphs of segments
- Mnëv's universality theorem revisited
- Most tensor problems are NP-hard
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- On the Complexity of Numerical Analysis
- Realizability of graphs and linkages
- Realization spaces of polytopes
- Some provably hard crossing number problems
- Tensor Decompositions and Applications
- Tensor rank is NP-complete
- The computational complexity of some problems of linear algebra
Cited in
(24)- Several remarks on tensor rank computation
- Length Complexity of Tensor Products
- Rank of a tensor and quantum entanglement
- Typical tensorial rank
- On the tensor rank of the \(3 \times 3\) permanent and determinant
- Most tensor problems are NP-hard
- On the average condition number of tensor rank decompositions
- Barriers for rank methods in arithmetic complexity
- scientific article; zbMATH DE number 7561763 (Why is no real title available?)
- Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
- Topological art in simple galleries
- Solving the tensor isomorphism problem for special orbits with low rank points: cryptanalysis and repair of an Asiacrypt 2023 commitment scheme
- Tensor codes for the rank metric
- On the complexity of finding tensor ranks
- Hankel Tensor Decompositions and Ranks
- Tensor rank is NP-complete
- Non-interactive commitment from non-transitive group actions
- Notions of tensor rank
- Tensor rank is hard to approximate
- The complexity of tensor circuit evaluation
- Monomial isomorphism for tensors and applications to code equivalence problems
- On classifying continuous constraint satisfaction problems
- scientific article; zbMATH DE number 7387190 (Why is no real title available?)
- The complexity of recognizing geometric hypergraphs
This page was built for publication: The complexity of tensor rank
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722207)
