On Counting AC0 Circuits with Negative Constants
On Counting AC0 Circuits with Negative Constants
复制标题
具有负常数的 AC0 电路计数
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
H. LeThanh
中科院分区：
文献类型：
--
作者：
A. Ambainis;D. M. Barrington;H. LeThanh
继续Agrawal等人[1]对TC 0、AC 0与算术电路之间关系的研究，回答了本文中几个未解决的问题。我们的主要结果是，类DiffAC 0和GapAC 0一致，下多时间，对数空间，对数时间的一致性。由此我们可以得出，在对数空间均匀性下，以下等式成立：etse 409 - 01 etse
Continuing the study of the relationship between TC 0, AC 0 and arithmetic circuits, started by Agrawal et al. [1], we answer a few questions left open in this paper. Our main result is that the classes DiffAC 0 and GapAC 0 coincide, under poly-time, log-space, and log-time uniformity. From that we can derive that under logspace uniformity, the following equalities hold: etse409-01etse