Frage

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?

Keine korrekte Lösung

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top