The complexity of tensor calculus (Q1413648)

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.