# What is the comparator circuit?

The standard circuits $$AC^i$$, $$NC^i$$ are constructed using $$AND$$, $$OR$$ and $$NOT$$ of various fan-ins, fan-outs and depths.

What is the comparator gate constituted from?

Structurally why is it believed $$NC^i$$ is not in any $$CC^j$$ if $$i\geq 1$$ and why is it believed $$CC^i$$ is not in any $$NC^j$$ if $$i\geq 1$$ (refer https://arxiv.org/abs/1208.2721 for the conjecture $$NC$$ and $$CC$$ are incomparable)?

• Comparator circuits are described in the paper. You don't need us to help you read the paper. – Yuval Filmus Jun 9 at 8:30

A comparator circuit is a circuit computing a function on $$x_1,\ldots,x_n \in \{0,1\}^n$$. The inputs to the circuit are labeled with either constants ($$0$$ or $$1$$), inputs ($$x_1,\ldots,x_n$$) or negated inputs ($$\lnot x_1,\ldots,\lnot x_n$$). The only allowed gate is a comparator gate, which has two inputs $$a,b$$ and two outputs $$a\land b,a\lor b$$. The circuit has no fan-out, that is, an output cannot be duplicated. One of the "wires" is designated as an output (just like a usual circuit).
Equivalently, we can represent a comparator circuit as a "straight-line program" with $$m$$ variables $$z_1,\ldots,z_m$$, each initialized by a constant, an input, or a negated input. The program itself is a sequence of instructions of the form $$z_i,z_j \gets z_i \land z_j,z_i \lor z_j.$$ One of the variables $$z_o$$ is the output of the circuit.
• It appears $CC$ seems to be having identical straightline representation to any boolean circuit where number of instructions which do not erase the inputs is $0$. We can introduce dummy instructions $z\leftarrow z$ or $z\leftarrow{garbage}$ if we are not using the input variables $z$ again in the straightline representation of the boolean formula. – Bread Winner Jun 9 at 9:44