Let Mod$_3$ be the language of binary strings with the sum of the bits divisible by 3, and PRIMES be the set of prime integers.

In a 2001 paper A Lower Bound for Primality, Allender, Saks, and Shparlinski say that Mod$_3$ is AC$^0$ Turing-reducible to PRIMES, but ask whether it is possible to find an AC$^0$ many-one reduction from Mod$_3$ to PRIMES.

Has there been progress on this question?

A reduction from Mod$_3$ to PRIMES is easy by using the observation that 3 divides $4m + k$ iff 3 divides $m + k$, so 3 divides $n$ iff 3 divides the sum of the base-4 digits of $n$. This can be achieved by a logarithmic depth circuit, but for an AC$^0$ reduction one of course needs a fixed-depth circuit.

Allender et al. provide a probabilistic fixed-depth circuit for the reduction, and by Adleman's 1978 argument there must then exist a deterministic circuit that performs the same function. This yields a non-uniform AC$^0$ reduction.

(This question follows-on from Eric Allender's answer Are the problems PRIMES, FACTORING known to be P-hard? where he states that the lower bound for PRIMES of TC$^0$ has not been improved since their paper.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.