Pergunta

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?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top