Damm, Carsten; Holzer, Markus; McKenzie, Pierre The complexity of tensor calculus. (English) Zbl 1033.15025 Comput. Complexity 11, No. 1-2, 54-89 (2002). 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. Reviewer: Yueh-er Kuo (Knoxville) Cited in 1 ReviewCited in 9 Documents 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 Keywords:Tensor formula; permanent; complexity; counting classes; completeness; algebraic Turing machine; word problem; multilinear algebra; tensor calculus; Boolean semiring; polytime algorithm PDFBibTeX XMLCite \textit{C. Damm} et al., Comput. Complexity 11, No. 1--2, 54--89 (2002; Zbl 1033.15025) Full Text: DOI