TR99-010 Authors: Eric Allender, Igor E. Shparlinski, Michael Saks

Publication: 6th April 1999 11:55

Downloads: 1816

Keywords:

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.

In the revised version, we show that MAJORITY is also reducible

to Primes (and to GCD and to Square.Free).