期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We extend the lower bound techniques of [Fortnow], to the unbounded-error probabilistic model. A key step in the argument is a generalization of Nepomnjascii's theorem from the Boolean setting to the arithmetic setting. This generalization is made possible, due to the recent discovery of logspace-uniform TC^0 circuits for iterated multiplication. Here is an example of the sort of lower bounds that we obtain: we show that MajMajSAT is not contained in PrTiSp(n^{1+o(1)},n^e) for any e < 1. We also extend a lower bound of [Fortnow], from showing that co-SAT does not have uniform NC^1 circuits of size n^{1+o(1)}, to a similar result for SAC^1 circuits.
