TR00-036 Authors: Carsten Damm, Markus Holzer, Pierre McKenzie

Publication: 6th June 2000 18:23

Downloads: 1066

Keywords:

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.