ECCC-Report TR99-010https://eccc.weizmann.ac.il/report/1999/010Comments and Revisions published for TR99-010en-usMon, 21 Jun 1999 16:41:58 +0300
Comment 1
| An Improvement Comment on: TR99-010 |
Eric Allender
https://eccc.weizmann.ac.il/report/1999/010#comment1In the revised version, we show that MAJORITY is also reducible
to Primes (and to GCD and to Square.Free).
Mon, 21 Jun 1999 16:41:58 +0300https://eccc.weizmann.ac.il/report/1999/010#comment1
Paper TR99-010
| A Lower Bound for Primality |
Eric Allender,
Igor E. Shparlinski,
Michael Saks
https://eccc.weizmann.ac.il/report/1999/010Recent 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.
Tue, 06 Apr 1999 11:55:55 +0300https://eccc.weizmann.ac.il/report/1999/010