Circuit booléen de taille polynomiale pour compter le nombre de bits

Question

Étant donné un nombre naturel $ n geq 1 $, Je cherche un circuit booléen sur 2 $ $ variables, $ varphi (x_1, y_1, dots, x_n, y_n) $, de sorte que la sortie est vraie si et seulement si l'affectation qui le rend vrai vérifie

$$ sum_ {i = 1} ^ {i = n} (x_i + y_i) not equiv n bmod 3 $$

Je dois spécifier que je recherche un booléen circuit, pas nécessairement une formule booléenne car elle est généralement écrite sous forme normale conjonctive (CNF). En effet, lorsqu'il est écrit en CNF, une formule comme celle précédente a une représentation triviale où le nombre de clauses est approximativement $ frac {4 ^ n} {3} $, car il contient une clause pour chaque affectation $ (x_1, y_1, dots, x_n, y_n) $ dont les bits résument à une valeur conforme à $ n bmod 3 $. La construction d'une telle formule prendrait donc un temps exponentiel.

On m'a dit qu'un circuit booléen peut être trouvé pour cette formule qui accepte une représentation de la taille polynomiale en $ n $. Cependant, jusqu'à présent, je n'ai pas pu le trouver. J'utiliserais de l'aide; Merci.