期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Recent work by Bernasconi, Damm and Shparlinski
proved lower bounds on the circuit complexity of the square-free
numbers, and raised as an open question if similar (or stronger)
lower bounds could be proved for the set of prime numbers. In
this short note, we answer this question affirmatively, by showing
that the set of prime numbers (represented in the usual binary
notation) is not contained in \acp for any prime p. Similar
lower bounds are presented for the set of square-free numbers, and
for the problem of computing the greatest common divisor of two numbers.
