The complexity of tensor calculus
algebraic Turing machineBoolean semiringcompletenesscomplexitycounting classesmultilinear algebrapermanentpolytime algorithmtensor calculusTensor formulaword problem
Turing machines and related notions (03D10) Word problems, etc. in computability and recursion theory (03D40) Multilinear algebra, tensor calculus (15A69) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algebraic theory of languages and automata (68Q70) Combinatorics on words (68R15)
The authors study the word problem generalized to multilinear algebra expressed by tensors. They show that basic tensor calculus not only captures natural complexity classes in simple ways, but it yields simpler unified proofs of nonuniform inclusions formerly scattered in the literature. Their results concern tensors over semirings, including the Boolean semiring \(B= (\{0, 1\},\vee,\wedge)\), the fields of characteristic 2, and the natural numbers \(N= (\{0,1,\dots\},+,\bullet)\). The structure of the paper is as follows. In Section 2 the authors introduce the complexity classes needed in later sections. They also introduce the terminology and basic parsing techniques for tensor formulas. To support intuition they strictly base all the formalism on matrices rather than tensors. This is based on connections between multi-index tensor notation and two-index matrix notation, clarified in Section 3. In Section 4 they give a polytime algorithm to construct a tensor formula which evaluates to the permanent of a square matrix. Then in Section 5 they introduce algebraic Turning machines, and use this model in Section 6 to prove their completeness results. In Section 7 they give a unified and intuitive proof for the existence of nonuniform simulations between Boolean and arithmetic complexity classes. In the last section, they conclude and discuss related results.
- Tensor products and computability
- Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits
- The complexity of tensor circuit evaluation
- Characterizing Valiant's algebraic complexity classes
- A common algebraic description for probabilistic and quantum computations
- The arithmetic complexity of tensor contraction
- The arithmetic complexity of tensor contractions
- Length Complexity of Tensor Products
- New Algorithm for Tensor Calculation in Field Theories
- Generalized counting constraint satisfaction problems with determinantal circuits
- scientific article; zbMATH DE number 1834647 (Why is no real title available?)
- Algorithmic simplification of tensor expressions
- Tensor network complexity of multilinear maps
- Tensor network complexity of multilinear maps
- Theory and Computation of Complex Tensors and its Applications
- Most tensor problems are NP-hard
- The tensor hierarchy simplified
- On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
- Picturing Counting Reductions with the ZH-Calculus
- Well-tempered ZX and ZH calculi
- Tensor network rewriting strategies for satisfiability and counting
- Weighted automata and logics meet computational complexity
- A graphical \#SAT algorithm for formulae with small clause density
- Logical characterizations of weighted complexity classes
- Descriptive complexity and weighted Turing machines
- Tensor network contractions for \#SAT
This page was built for publication: The complexity of tensor calculus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1413648)
