title: Parity problem
text: # 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$
  