Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR00-036 | 29th May 2000 00:00

The Complexity of Tensor Calculus

TR00-036
Authors: Carsten Damm, Markus Holzer, Pierre McKenzie
Publication: 6th June 2000 18:23
Keywords:

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.

ISSN 1433-8092 | Imprint