Complexity of tensor calculus

Abstract

Tensor calculus over semirings is shown relevant to complexity theory in unexpected ways. First, evaluating well-formed tensor formulas with explicit tensor entries is shown complete for circle plusP, for NP, and for #P as the semiring varies. Indeed the permanent of a matrix is shown expressible as the value of a tensor formula in much the same way that Berkowitz's theorem expresses its determinant. Second, restricted tensor formulas are shown to capture the classes LOGCFL and NL, their parity counterparts circle plusLOGCFL and circle plusL, and several other counting classes. Finally, the known inclusions NP/poly subset of or equal to circle plusP/poly, LOGCFL/poly subset of or equal to circle plusLOGCFL/poly, and NL/poly subset of or equal to circle plusL/poly, which have scattered proofs in the literature (Valiant Vazirani 1986; Gaal & Wigderson 1996), are shown to follow from the new characterizations in a single blow. As an intermediate tool, we define and make use of the natural notion of an algebraic Turing machine over a semiring S.