Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-036 | 29th May 2000 00:00

The Complexity of Tensor Calculus


Authors: Carsten Damm, Markus Holzer, Pierre McKenzie
Publication: 6th June 2000 18:23
Downloads: 2183


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