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$ Commented Jun 9, 2021 at 8:30

1 Answer 1

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$
    – Turbo
    Commented Jun 9, 2021 at 9:32
  • $\begingroup$ The difference is that in usual circuits, we allow instructions which don’t erase the inputs. $\endgroup$ Commented Jun 9, 2021 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$
    – Turbo
    Commented Jun 9, 2021 at 9:44
  • $\begingroup$ You can implement CC using a usual circuit, but not the other way around. $\endgroup$ Commented Jun 9, 2021 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$ Commented Jun 9, 2021 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.