ECCC-Report TR00-036https://eccc.weizmann.ac.il/report/2000/036Comments and Revisions published for TR00-036en-usTue, 06 Jun 2000 18:23:31 +0300
Paper TR00-036
| The Complexity of Tensor Calculus |
Carsten Damm,
Markus Holzer,
Pierre McKenzie
https://eccc.weizmann.ac.il/report/2000/036Tensor 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.
Tue, 06 Jun 2000 18:23:31 +0300https://eccc.weizmann.ac.il/report/2000/036