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, this question is important for computation inside the computer game Dwarf Fortress.
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.
(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
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.
