×

The complexity of tensor calculus. (English) Zbl 1033.15025

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.

MSC:

15A69 Multilinear algebra, tensor calculus
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D10 Turing machines and related notions
03D40 Word problems, etc. in computability and recursion theory
68R15 Combinatorics on words
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q70 Algebraic theory of languages and automata
PDFBibTeX XMLCite
Full Text: DOI