期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Continuing the study of the relationship between TC0,
AC0 and arithmetic circuits, started by Agrawal et al.
(IEEE Conference on Computational Complexity'97),
we answer a few questions left open in this
paper. Our main result is that the classes DiffAC0 and
GapAC0 coincide, under poly-time, log-space, or log-time
uniformity. From that we can derive that under logspace
uniformity, the following equalities hold:
C=AC0=PAC0=TC0
