Parity problem
# Parity problem

The term parity problem may refer to:

* Parity problem (sieve theory), the question of how many primes less than a given integer have an even (or odd) number of prime factors
* The problem of recognizing the formal language consisting of bitstrings which contain an even number of 1 bits. This language is regular, but it is famously not in $AC^0$
