5
$\begingroup$

Is a lower bound of $\Omega(n^2)$ known for the size of any constant depth circuit expressing a digital comparator for two $n$-bit numbers?

Two $n$-bit binary numbers can be compared using a digital comparator circuit. The straightforward way to implement such a circuit is to compare the high-order bits; if they are the same then continue to compare the second most significant bits, and so on. This circuit has size (measured in the number of gates) that is roughly quadratic in $n$, with linear depth. By standard arguments, this can be folded up into an equivalent circuit of roughly the same size that has logarithmic depth (in $n$).

In fact, constant depth circuits of size $O(n^2)$ are sufficient for a digital comparator, if unbounded fan-in gates are allowed: see Heribert Vollmer's Introduction to Circuit Complexity (Exercise 1.4). Is a tight lower bound known?

$\endgroup$
2
$\begingroup$

Comparison can be implemented by subtracting twos-complement numbers and then testing whether the most significant bit is 0 or 1. Subtraction can be implemented as addition ($x-y = x + \overline{y} + 1$, where $\overline{y}$ is obtained by flipping all bits of $y$). Addition can be implemented using carry-lookahead methods.

If you put all this together, I think you get a comparison circuit that uses $O(n)$ gates and has constant depth.

In particular, let $g_i = a_i \land b_i$ ("generate"), $p_i = a_i \lor b_i$ ("propagate"), $q_i = p_{i+1} \lor \cdots \lor p_{n-1}$, $t_i = g_i \land q_i$, and $c_{n-1} = t_0 \lor \cdots \lor t_{n-2}$ ("carry"). This lets you compute the carry into the most significant bit in constant-depth and $O(n)$ gates. That's all you need for the results of the comparison (you don't need to compute the value of the other bits of the sum). The reason this requires fewer gates than a full addition or full subtraction is that we only need the carry into the most significant bit, not all the carry bits.

Double-check my reasoning -- I could have gone awry somewhere.

$\endgroup$
  • $\begingroup$ Yes, I thought the same: COMPARISON is equivalent within a constant factor to finding the MSB. It is weird that most literature claimed unbounded fan-in COMPARISON is of quadratic size and constant depth, but it seems to that the wire complexity is quadratic instead of the size. $\endgroup$ – Willard Zhan Feb 11 '17 at 10:26
  • $\begingroup$ They probably assume bounded fan-in for the gates: as I understand it, you are using gates with fan-in $O(n)$, which require $\log n$ depth with bounded fan-in. As far as I know, adder implementations with $O(n)$ size require $O(\log n)$ depth. $\endgroup$ – Gabriel Gouvine Feb 12 '17 at 15:55

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.