<p>(the answer is not eligible because it refers to separate AND, OR gates without fan out restriction)</p>

<p>The following article is on topic: <a href="http://arxiv.org/abs/cond-mat/9701118" rel="nofollow">Majority-Vote Cellular Automata, Ising Dynamics, and P-Completeness</a></p>

<blockquote>
  <p>We show that in three or more dimensions <strong>these systems can simulate
  Boolean circuits of AND and OR gates, and are therefore P-complete</strong>.
  That is, predicting their state t time-steps in the future is at least
  as hard as any other problem that takes polynomial time on a serial
  computer.</p>
  
  <p>(...)</p>
  
  <p>The Monotone Circuit Value problem, where AND and OR gates are allowed
  but NOT gates are not, is still P-complete for the following reason:
  using De Morgan’s laws (...), we can shift negations
  back through the gates until they only affect the inputs themselves.
  Thus any Circuit Value problem can be converted to a Monotone Circuit
  Value problem with some of the inputs negated. This kind of
  conversion, from an instance of one problem to an instance of another,
  is called a reduction.</p>
</blockquote>

CC BY-SA 3.0
2012-03-25T16:02:30.193Z
Could you please elaborate your answer? I failed to see the connection between "these systems" and the AND&OR circuits mentioned above.
Dai Le
CC BY-SA 3.0
2012-03-25T16:09:35.513Z
I have read the paper 2 years ago. It is devoted to P-completeness and monotone logic circuits. I leave final interpretation to reader, because I can't remember details now. It is for sure a good article though, especially if Itai seems to be confused. More: isn't the bold text in my quote the answer – that AND/OR logic circuits are P-complete?
Mooncer
CC BY-SA 3.0
2012-03-25T16:22:56.027Z
Ok you are right. I will maybe leave my answer, maybe it will be helpful to someone.
Mooncer
CC BY-SA 3.0
2012-03-25T16:24:27.293Z
It is a well-known fact that the problem of evaluating monotone circuits which consist of AND gates and OR gates, where each gate is allowed to have **fanout 2**, is P-complete. The circuit problem mentioned by the orignal poster imposes **fanout restriction**, and thus it's not know to be P-complete.
Dai Le
CC BY-SA 3.0
2012-09-04T14:58:07.050Z
@dai do you have a ref for that? seems like fanout 2 could allow arbitrary DAGs. is that not right?
vzn
CC BY-SA 3.0
2012-09-04T15:10:46.483Z
@vzn Circuit evaluation is in P. A reference for the fact Dai mentioned is Cook and Nguyen's book "Logical foundations of proof complexity".
Yuval Filmus
CC BY-SA 3.0
2012-03-25T15:50:29.810Z
2012-03-25T16:23:54.997Z
2012-03-25T16:23:54.997Z
Mooncer
<p>If I don't misunderstand what you mean by AND&amp;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)$. </p>

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

<p><img src="https://i.sstatic.net/TEuV1.png" alt="enter image description here"></p>

<p>We can define the <em>comparator circuit value problem</em> (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 <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:C#cc" rel="noreferrer">CC</a>, whose complete problems include natural problems like lex-first maximal matching, stable marriage, stable roomate. </p>

<p>In <a href="http://arxiv.org/abs/1208.2721" rel="noreferrer">this recent paper</a>, 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 <a href="http://en.wikipedia.org/wiki/SC_%28complexity%29" rel="noreferrer">SC</a> are incomparable.</p>

CC BY-SA 3.0
2012-03-25T15:21:14.050Z
2012-09-03T23:54:55.907Z
2012-09-03T23:54:55.907Z
Dai Le
<p>The AND&amp;OR gate is a gate which is given two inputs and returns their AND and their OR. Are circuits made only out of the AND&amp;OR gate, without fanout, capable of doing arbitrary computations? More precisely, is polynomial time computation logspace reducible to AND&amp;OR circuits?</p>

<p>My motivation for this problem is rather strange. As described <a href="http://www.bay12forums.com/smf/index.php?topic=104772.0">here</a>, this question is important for computation inside the computer game <a href="http://en.wikipedia.org/wiki/Dwarf_Fortress">Dwarf Fortress</a>.</p>

CC BY-SA 3.0
2012-03-25T13:01:31.483Z
Such circuits are monotone, and hence are far from P-complete.
David Harris
CC BY-SA 3.0
2012-03-25T13:33:11.303Z
@David Harris: At first sight, I thought so, too, but that reasoning is not correct because a log-space reduction can augment the input with its negation!
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-25T14:28:43.513Z
It can be, note that the monotone Boolean formula evaluation is complete for $\sf{NC^1}$ under $\sf{AC^0}$.
Kaveh
<cc.complexity-theory><circuit-complexity>
Are AND&OR circuits P-complete?
Itai Bar-Natan
# Are AND&OR circuits P-complete?

(Asked by: username_0 on 2012-03-25)

The AND&OR gate is a gate which is given two inputs and returns their AND and their OR. Are circuits made only out of the AND&OR gate, without fanout, capable of doing arbitrary computations? More precisely, is polynomial time computation logspace reducible to AND&OR circuits?

My motivation for this problem is rather strange. As described [here](http://www.bay12forums.com/smf/index.php?topic=104772.0), this question is important for computation inside the computer game [Dwarf Fortress](http://en.wikipedia.org/wiki/Dwarf_Fortress).

**Tags:** cc.complexity-theory, circuit-complexity

> **Comments:**
> **username_1**: Such circuits are monotone, and hence are far from P-complete.  
> **username_2**: @username_1: At first sight, I thought so, too, but that reasoning is not correct because a log-space reduction can augment the input with its negation!  
> **username_3**: It can be, note that the monotone Boolean formula evaluation is complete for $\sf{NC^1}$ under $\sf{AC^0}$.  

---

## 2 answers

### Answer by username_5 on 2012-03-25. Score: 24 | Accepted 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).

![enter image description here](https://i.sstatic.net/TEuV1.png)

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](http://qwiki.stanford.edu/index.php/Complexity_Zoo:C#cc), whose complete problems include natural problems like lex-first maximal matching, stable marriage, stable roomate.

In [this recent paper](http://arxiv.org/abs/1208.2721), Steve Cook, username_7 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](http://en.wikipedia.org/wiki/SC_%28complexity%29) are incomparable.


---

### Answer by username_4 on 2012-03-25. Score: 0

(the answer is not eligible because it refers to separate AND, OR gates without fan out restriction)

The following article is on topic: [Majority-Vote Cellular Automata, Ising Dynamics, and P-Completeness](http://arxiv.org/abs/cond-mat/9701118)

> We show that in three or more dimensions **these systems can simulate
> Boolean circuits of AND and OR gates, and are therefore P-complete**.
> That is, predicting their state t time-steps in the future is at least
> as hard as any other problem that takes polynomial time on a serial
> computer.
>
> (...)
>
> The Monotone Circuit Value problem, where AND and OR gates are allowed
> but NOT gates are not, is still P-complete for the following reason:
> using De Morgan’s laws (...), we can shift negations
> back through the gates until they only affect the inputs themselves.
> Thus any Circuit Value problem can be converted to a Monotone Circuit
> Value problem with some of the inputs negated. This kind of
> conversion, from an instance of one problem to an instance of another,
> is called a reduction.

> **Comments:**
> **username_5**: Could you please elaborate your answer? I failed to see the connection between "these systems" and the AND&OR circuits mentioned above.  
> **username_4**: I have read the paper 2 years ago. It is devoted to P-completeness and monotone logic circuits. I leave final interpretation to reader, because I can't remember details now. It is for sure a good article though, especially if Itai seems to be confused. More: isn't the bold text in my quote the answer – that AND/OR logic circuits are P-complete?  
> **username_4**: Ok you are right. I will maybe leave my answer, maybe it will be helpful to someone.  
> **username_5**: It is a well-known fact that the problem of evaluating monotone circuits which consist of AND gates and OR gates, where each gate is allowed to have **fanout 2**, is P-complete. The circuit problem mentioned by the orignal poster imposes **fanout restriction**, and thus it's not know to be P-complete.  
> **username_6**: @dai do you have a ref for that? seems like fanout 2 could allow arbitrary DAGs. is that not right?  
> **username_7**: @username_6 Circuit evaluation is in P. A reference for the fact Dai mentioned is Cook and Nguyen's book "Logical foundations of proof complexity".  

---

