1
$\begingroup$

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)?

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

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 is believed that CC and NC are incomparable since nobody managed to show that one of them is contained in the other. Usually, such inclusions are either easy or false, though sometimes this intuition is wrong (the best example is SL=L).

$\endgroup$
14
  • $\begingroup$ The straightline representation is interesting but so can any Boolean formula be given as a straightline having negated inputs and OR and AND gates and we can reuse variables and if we desire to keep number of variables in every layer similar we can update the unused variables in a dummy manner. $\endgroup$ – Bread Winner Jun 9 at 9:32
  • $\begingroup$ The difference is that in usual circuits, we allow instructions which don’t erase the inputs. $\endgroup$ – Yuval Filmus Jun 9 at 9:37
  • $\begingroup$ 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. $\endgroup$ – Bread Winner Jun 9 at 9:44
  • $\begingroup$ You can implement CC using a usual circuit, but not the other way around. $\endgroup$ – Yuval Filmus Jun 9 at 9:46
  • 1
    $\begingroup$ If the fan-out is 1 then you have a formula. They can be simulated in CC. It is conjectured that formulas are less powerful than circuits (in terms of complexity). $\endgroup$ – Yuval Filmus Jun 9 at 9:54

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.