Return to Answer

If I don't misunderstand what you mean by AND&OR gate, it is basically a comparator gate which takes two input bits $x$ and $y$ and produces two output bits $x\wedge y$ and $x\vee y$. The two output bits $x\wedge y$ and $x\vee y$ are basically min$(x,y)$ and max$(x,y)$.

Comparator circuits are built by composing these comparator gates together but allowing no more fan-outs other than the two outputs produced by each gate. Thus, we can draw comparator circuits using the notations below (similarly to how we draw sorting networks).

We can define the comparator circuit value problem (CCV) as follows: given a comparator circuit with specified Boolean inputs, determine the output value of a designated wire. By taking the closure of this CCV problem under logspace reductions, we get the complexity class CC, whose complete problems include natural problems like lex-first maximal matching, stable marriage, stable roomate. Together with my coauthors Steve Cook, Yuval Filmus and Yuli Ye, we showed recently that even when we use AC$^0$ many-one closure, we still get the same class CC. To the best of our knowledge at this point, NL $\subseteq$ CC $\subseteq$ P. But CC is neither known to be in NC nor P-complete.

If I don't misunderstand what you mean by AND&OR gate, it is basically a comparator gate which takes two input bits $x$ and $y$ and produces two output bits $x\wedge y$ and $x\vee y$. The two output bits $x\wedge y$ and $x\vee y$ are basically min$(x,y)$ and max$(x,y)$.

Comparator circuits are built by composing these comparator gates together but allowing no more fan-outs other than the two outputs produced by each gate. Thus, we can draw comparator circuits using the notations below (similarly to how we draw sorting networks).

We can define the comparator circuit value problem (CCV) as follows: given a comparator circuit with specified Boolean inputs, determine the output value of a designated wire. By taking the closure of this CCV problem under logspace reductions, we get the complexity class CC, whose complete problems include natural problems like lex-first maximal matching, stable marriage, stable roomate.

In this recent paper, Steve Cook, Yuval Filmus and I showed that even when we use AC$^0$ many-one closure, we still get the same class CC. To the best of our knowledge at this point, NL $\subseteq$ CC $\subseteq$ P. In our paper, we provided evidence that CC and NC are incomparable (so that CC is a proper subset of P), by giving oracle settings where relativized CC and relativized NC are incomparable. We also gave evidence that CC and SC are incomparable.

If I don't misunderstand what you mean by AND&OR gate, it is basically a comparator gate which takes two input bits $x$ and $y$ and produces two output bits $x\wedge y$ and $x\vee y$. The two output bits $x\wedge y$ and $x\vee y$ are basically min$(x,y)$ and max$(x,y)$.

Comparator circuits are built by composing these comparator gates together but allowing no more fan-outs other than the two outputs produced by each gate. Thus, we can draw comparator circuits using the notations below (similarly to how we draw sorting networks).

We can define the comparator circuit value problem (CCV) as follows: given a comparator circuit with specified Boolean inputs, determine the output value of a designated wire. By taking the closure of this CCV problem under logspace reductions, you get the complexity class CC, whose complete problems include natural problems like lex-first maximal matching, stable marriage, stable roomate. Together with my coauthors Steve Cook, Yuval Filmus and Yuli Ye, we showed recently that even when we use AC$^0$ many-one closure, we still get the same class CC. To the best of our knowledge at this point, NL $\subseteq$ CC $\subseteq$ P. But CC is neither known to be in NC nor P-complete.

If I don't misunderstand what you mean by AND&OR gate, it is basically a comparator gate which takes two input bits $x$ and $y$ and produces two output bits $x\wedge y$ and $x\vee y$. The two output bits $x\wedge y$ and $x\vee y$ are basically min$(x,y)$ and max$(x,y)$.

Comparator circuits are built by composing these comparator gates together but allowing no more fan-outs other than the two outputs produced by each gate. Thus, we can draw comparator circuits using the notations below (similarly to how we draw sorting networks).

We can define the comparator circuit value problem (CCV) as follows: given a comparator circuit with specified Boolean inputs, determine the output value of a designated wire. By taking the closure of this CCV problem under logspace reductions, we get the complexity class CC, whose complete problems include natural problems like lex-first maximal matching, stable marriage, stable roomate. Together with my coauthors Steve Cook, Yuval Filmus and Yuli Ye, we showed recently that even when we use AC$^0$ many-one closure, we still get the same class CC. To the best of our knowledge at this point, NL $\subseteq$ CC $\subseteq$ P. But CC is neither known to be in NC nor P-complete.

If I don't misunderstand what you mean by AND&OR gate, it is basically a comparator gate which takes two input bits $x$ and $y$ and produces two output bits $x\wedge y$ and $x\vee y$. The two output bits $x\wedge y$ and $x\vee y$ are basically min$(x,y)$ and max$(x,y)$.

Comparator circuits are built by composing these comparator gates together but allowing no more fan-outs other than the two outputs produced by each gate. Thus, we can draw comparator circuits using the notations below (similarly to how we draw sorting networks).

We can define the comparator circuit value problem (CCV) as follows: given a comparator circuit with specified Boolean inputs, determine the output value of a designated wire. By taking the closure of this CCV problem under logspace reductions, you get the complexity class CC, whose complete problems include natural problems like lex-first maximal matching, stable marriage, stable roomate. Together with my coauthors Steve Cook, Yuval Filmus and Yuli Ye, we showed recently that even when we use AC$^0$ many-one closure, we still get the same class CC. To the best of our knowledge at this point, NL $\subseteq$ CC $\subseteq$ P. But CC is neither known to be in NC nor P-complete.

If I don't misunderstand what you mean by AND&OR gate, it is basically a comparator gate which takes two input bits $x$ and $y$ and produces two output bits $x\wedge y$ and $x\vee y$. The two output bits $x\wedge y$ and $x\vee y$ are basically min$(x,y)$ and max$(x,y)$.

Comparator circuits are built by composing these comparator gates together but allowing no more fan-outs other than the two outputs produced by each gate. Thus, we can draw comparator circuits using the notations below (similarly to how we draw sorting networks).

We can define the comparator circuit value problem (CCV) as follows: given a comparator circuit with specified Boolean inputs, determine the output value of a designated wire. By taking the closure of this CCV problem under logspace reductions, you get the complexity class CC, whose complete problems include natural problems like lex-first maximal matching, stable marriage, stable roomate. Together with my coauthors Steve Cook, Yuval Filmus and Yuli Ye, we showed recently that even when we use AC$^0$ many-one closure, we still get the same class CC. To the best of our knowledge at this point, NL $\subseteq$ CC $\subseteq$ P. But CC is neither known to be in NC nor P-complete.