-- May 10 In-Class Exercise
Without `MOD3` gates, we can calculate parity by tabulating all possible `2^n` outputs and representing it as a CNF formula. As we allow unbounded fan-in, this circuit will be of depth 2. The first layer of fan-in AND will be of up to size `1.5n*2^n` - every output is negated in half the inputs. Negation requires an additional circuit, leading to an average size of `1.5n` for each AND. There are `2^n` AND circuits OR'd together.
I don't use `MOD3` gates so far.
Without @BT@MOD3@BT@ gates, we can calculate parity by tabulating all possible @BT@2^n@BT@ outputs and representing it as a CNF formula. As we allow unbounded fan-in, this circuit will be of depth 2. The first layer of fan-in AND will be of up to size @BT@1.5n*2^n@BT@ - every output is negated in half the inputs. Negation requires an additional circuit, leading to an average size of @BT@1.5n@BT@ for each AND. There are @BT@2^n@BT@ AND circuits OR'd together.
I don't use @BT@MOD3@BT@ gates so far.