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 and acknowledge you have read our privacy policy.