Lower Bounds for Tropical Circuits and Dynamic Programs
Lower Bounds for Tropical Circuits and Dynamic Programs
复制标题
热带回路和动态程序的下限
DOI：
10.1007/s00224-014-9574-4
复制
发表时间：
2015
影响因子：
0.5
通讯作者：
S. Jukna
中科院分区：
文献类型：
--
作者：
S. Jukna
热带回路是以最小值和加号或最大值和加号操作作为门的回路。它们的重要性源于它们与动态规划算法的密切关系。热带电路的能力介于单调布尔电路和单调算术电路之间。在本文中，我们提出了一些下界参数热带电路，因此，动态程序。
Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower bounds arguments for tropical circuits, and hence, for dynamic programs.
登录
查看更多内容
论公式的深度复杂度
DOI：
10.1007/bf01744302
发表时间：
1979
期刊：
Mathematical systems theory
影响因子：
--
作者：
E. Shamir;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：
--
发表时间：
2005
期刊：
影响因子：
--
作者：
S. Gashkov;I. Gashkov
通讯作者：
I. Gashkov
Об одном методе получения нижних оценок сложности монотонных арифметических схем, 一种获得计算实多项式的单调算术电路复杂度下界的方法
DOI：
10.4213/sm7904
发表时间：
2012
期刊：
Matematicheskii Sbornik
影响因子：
--
作者：
С.Б. Гашков;S. B. Gashkov;Игорь Сергеевич Сергеев;I. S. Sergeev
通讯作者：
I. S. Sergeev