1
$\begingroup$

Why sum of two binary numbers cannot be determined in $NC^0$ but it can be determined in $AC^0$?

$\endgroup$
2
$\begingroup$

In an $\mathsf{NC^0}$ circuit, every output bit depends on a bounded number of input bits. But the $k$th bit of the output (counting from the LSB) depends on the first $k$th bits of each input.

To see that $\mathsf{AC^0}$ circuits can compute addition, we need to produce such a circuit. Hopefully you have seen such circuits, and otherwise perhaps you can construct them on your own. Give it a shot.

$\endgroup$
1
$\begingroup$

an $NC^0$ can only consider circuits of fan-in 2. If we try to adding with a Full-Adder with Lookahead Gatter to calculate the carry, needs every Full-Adder 3 Input signals. But in $NC^0$ are only 2 inputs allowed. If we try to replace Full-Adder with other logic gatters, we hurt the depth of the circuit.

enter image description here

image-source: https://upload.wikimedia.org/wikipedia/commons/thumb/0/04/4-bit_carry_lookahead_adder.svg/1000px-4-bit_carry_lookahead_adder.svg.png

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.