Lower bounds for monotone counting circuits
Lower bounds for monotone counting circuits
复制标题
单调计数电路的下界
DOI：
10.1016/j.dam.2016.04.024
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Jukna
中科院分区：
文献类型：
--
作者：
S. Jukna
一个单调算术电路计算一个给定的多元多项式f，如果它在所有非负整数输入上的值与f的值相同。如果0-1输入成立，电路计算f；在其他输入上，电路可以输出任意值。电路决定f是否有与f相同的0-1根。我们首先表明，一些多线性多项式的计数比计算它们更容易指数化，而一些多项式的确定比计数更容易指数化。我们的主要结果是计数电路大小的一般下界。
A monotone arithmetic circuit computes a given multivariate polynomial f if its values on all nonnegative integer inputs are the same as those of f. The circuit counts f if this holds for 0–1 inputs; on other inputs, the circuit may output arbitrary values. The circuit decides f if it has the same 0–1 roots as f. We first show that some multilinear polynomials can be exponentially easier to count than to compute them, and that some polynomials can be exponentially easier to decide than to count them. Our main results are general lower bounds on the size of counting circuits.
登录
查看更多内容
论公式的深度复杂度
DOI：
10.1007/bf01744302
发表时间：
1979
期刊：
Mathematical systems theory
影响因子：
--
作者：
E. Shamir;M. Snir
通讯作者：
M. Snir
单调算术电路的尺寸深度权衡
DOI：
10.1016/0304-3975(91)90173-y
发表时间：
1991
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
M. Snir
通讯作者：
M. Snir
Shamir 和 Snir 单调电路深度下界的直接版本
DOI：
10.1016/0020-0190(94)90061-2
发表时间：
1994
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
Prasoon Tiwari;M. Tompa
通讯作者：
M. Tompa
否定的力量可以呈指数级增长
DOI：
10.1145/800135.804412
发表时间：
1979
期刊：
Proceedings of the eleventh annual ACM symposium on Theory of computing
影响因子：
--
作者：
L. Valiant
通讯作者：
L. Valiant
Об одном методе получения нижних оценок сложности монотонных арифметических схем, 一种获得计算实多项式的单调算术电路复杂度下界的方法
DOI：
10.4213/sm7904
发表时间：
2012
期刊：
Matematicheskii Sbornik
影响因子：
--
作者：
С.Б. Гашков;S. B. Gashkov;Игорь Сергеевич Сергеев;I. S. Sergeev
通讯作者：
I. S. Sergeev