21
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Such circuits are monotone, and hence are far from P-complete. $\endgroup$ – David Harris Mar 25 '12 at 13:01
  • 3
    $\begingroup$ @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! $\endgroup$ – Tsuyoshi Ito Mar 25 '12 at 13:33
  • 2
    $\begingroup$ It can be, note that the monotone Boolean formula evaluation is complete for $\sf{NC^1}$ under $\sf{AC^0}$. $\endgroup$ – Kaveh Mar 25 '12 at 14:28
23
$\begingroup$

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

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.

$\endgroup$
0
$\begingroup$

(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.

$\endgroup$
  • $\begingroup$ Could you please elaborate your answer? I failed to see the connection between "these systems" and the AND&OR circuits mentioned above. $\endgroup$ – Dai Le Mar 25 '12 at 16:02
  • $\begingroup$ 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? $\endgroup$ – Mooncer Mar 25 '12 at 16:09
  • $\begingroup$ Ok you are right. I will maybe leave my answer, maybe it will be helpful to someone. $\endgroup$ – Mooncer Mar 25 '12 at 16:22
  • 3
    $\begingroup$ 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. $\endgroup$ – Dai Le Mar 25 '12 at 16:24
  • 2
    $\begingroup$ @vzn Circuit evaluation is in P. A reference for the fact Dai mentioned is Cook and Nguyen's book "Logical foundations of proof complexity". $\endgroup$ – Yuval Filmus Sep 4 '12 at 15:10

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.