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 $\olpus\P$, 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' theorem expresses its determinant. Second, restricted tensor formulas are shown to capture the classes $\LOGCFL$ and $\NL$, their parity counterparts $\oplus\LOGCFL$ and $\oplus\L$, and several other counting classes. Finally, the known inclusions $\NP/\poly \subseteq \oplus\P/\poly$, $\LOGCFL/\poly \subseteq \oplus\LOGCFL/\poly$, and $\NL/\poly \subseteq \oplus\L/\poly$, which have scattered proofs in the literature (Gal and Wigderson 1996, Valiant and Vazirani 1986), are shown to follow from the new characterizations in a single blow.