| Abstract (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Recent work by Bernasconi, Damm and Shparlinski showed that the set of square-free numbers is not in AC 0, and raised as an open question if similar (or stronger) lower bounds could be proved for the set of prime numbers. In this note, we show that the Boolean majority function is AC 0-Turing reducible to the set of prime numbers (represented in binary). From known lower bounds on Maj (due to Razborov and Smolensky) we conclude that primality can not be tested in AC 0 [p] for any prime p. Similar results are obtained for the set of squarefree numbers, and for the problem of computing the greatest common divisor of two numbers. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||