期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Tensor calculus over semirings is shown releva
algebraic complexity theory, nonuniformity, permanent, tensor calculus nt 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
\LOGCFL and \L, and several other counting classes. Finally,
the known inclusions \NP\poly\P\poly , \LOGCFL\poly\LOGCFL\poly , and \NL\poly\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.
