Dimensione polinomiale Circuito booleano per il conteggio del numero di bit

Question

Dato un numero naturale $ n geq 1 $, Sto cercando un circuito booleano $ 2n $ variabili, $ varphi (x_1, y_1, dots, x_n, y_n) $, in modo tale che l'output sia vero se e solo se l'incarico che lo rende vero verifica

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

Dovrei specificare che questo sto cercando un booleano circuito, non necessariamente una formula booleana in quanto di solito è scritta in forma normale congiuntiva (CNF). Questo perché quando scritto in CNF, una formula come quella prima ha una rappresentazione banale in cui il numero di clausole è approssimativamente $ frac {4^n} {3} $, poiché contiene una clausola per ogni incarico $ (x_1, y_1, dots, x_n, y_n) $ i cui pezzi si sommano a un valore congruente con $ n bmod 3 $. La costruzione di tale formula richiederebbe quindi tempo esponenziale.

Mi è stato detto che un circuito booleano può essere trovato per questa formula che accetta una rappresentazione del polinomio di dimensioni in $ n $. Tuttavia, finora non sono stato in grado di trovarlo. Vorrei usare un po 'di aiuto; Grazie.