The complexity of tensor calculus

The complexity of tensor calculus
复制标题

张量微积分的复杂性

DOI：
--
复制
发表时间：
2000
期刊：
Proceedings 15th Annual IEEE Conference on Computational Complexity
影响因子：
--
通讯作者：
P. McKenzie
P. McKenzie
中科院分区：
--
文献类型：
--
作者：
C. Damm;M. Holzer;P. McKenzie

文献摘要

被引文献

相似文献

半环上的张量演算与复杂性有关 理论以意想不到的方式。首先，计算良型张量 具有显式张量项的公式对于$igoplusP$，对于NP， 当半环变化时，实际上是矩阵的永久性 可以表示为张量公式的值， Berkowitz定理表示行列式的方式。第二，限制 张量公式显示为捕获类LOGCFL和 NL，其平价对应物$igoplusLOGCFL$和$IgoplusL$和其他几种 数课最后，已知的内含物$NP/多子集 igoplusP/poly$，$LOGCFL/poly subseteq igoplusLOGCFL/poly$和$NL/poly subseteq igoplusL/poly$， 在文献中有零散的证据（Valiant & Vazirani 1986; Gál & Wigderson 1996），表明遵循新的特征 在一个单一的打击。作为中间工具，我们定义并使用 半环$ mathcal{S}$上代数图灵机的自然概念。
AbstractTensor 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 $igoplusP$, 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’s theorem expresses its determinant. Second, restricted tensor formulas are shown to capture the classes LOGCFL and NL, their parity counterparts $igoplusLOGCFL$ and $igoplusL$, and several other counting classes. Finally, the known inclusions $NP/poly subseteq igoplusP/poly$, $LOGCFL/poly subseteq igoplusLOGCFL/poly$, and $NL/poly subseteq igoplusL/poly$, which have scattered proofs in the literature (Valiant & Vazirani 1986; Gál & Wigderson 1996), are shown to follow from the new characterizations in a single blow. As an intermediate tool, we define and make use of the natural notion of an algebraic Turing machine over a semiring $ mathcal{S}$.