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.