1
$\begingroup$

I am trying to prove the above statement. A DeMorgan circuit is a circuit that has only $\{ \wedge, \vee, \neg \}$ gates, and the negation is applied only to input variables.

So, assuming we have a circuit of size $s$ that computes a function $f: \{0,1\}^n \rightarrow \{0,1\}$. The basis for this circuit is $\{\wedge, \vee, \neg\}$ with fan-in 2 for the OR and AND gates. I am trying to prove we can convert this circuit to a DeMorgan circuit of size at most $2s$.

Intuitively and in small examples, this claim makes sense to me but I would like to prove that more formally. I have searched in several papers but this claim is mostly mentioned but not proved. Can someone give me intuition about the proof?

The above statement was mentioned in the following paper https://eccc.weizmann.ac.il/report/2018/154/ in the second paragraph of the 1st page and continuing on the 2nd page.

Improve this question
$\endgroup$
5
  • $\begingroup$ If the fan-in is constant, you can get $O(s)$ by replacing each non-de Morgan gate with a constant size circuit computing the same function. $\endgroup$
    – Yuval Filmus
    Commented May 28, 2021 at 6:57
  • $\begingroup$ @YuvalFilmus you have to beware though, just applying de-morgan's law can exponentially increase the circuit size (each NOT will doubled, for every gate we apply the law on) $\endgroup$
    – nir shahar
    Commented May 29, 2021 at 11:23
  • $\begingroup$ I don't think so. It's a gadget reduction. Every gate is replaced by a constant size gadget. $\endgroup$
    – Yuval Filmus
    Commented May 29, 2021 at 11:44
  • $\begingroup$ @YuvalFilmus all "NOT" gates need to be only in the input, so when you do some transformation [ for example: NOT($a$ AND $b$) into (NOT $a$) OR (NOT $b$) ] you have to pass the NOT gates backwards and apply the transformation until the NOT reaches the inputs. Basically, in this way - each NOT will duplicate itself $2^d$ times where $d$ is the depth of that NOT gate $\endgroup$
    – nir shahar
    Commented May 29, 2021 at 11:51
  • $\begingroup$ I don’t think so. For every gate in the original circuit, you keep two gates, one computing the original function, and the other its negation. $\endgroup$
    – Yuval Filmus
    Commented May 29, 2021 at 12:32

1 Answer 1

Reset to default
2
$\begingroup$

The idea is to "move backwards" all the not gate. Assume you have some circuit, for example $(\cdot,\cdot)\rightarrow AND\rightarrow NOT\rightarrow OUTPUT$

Can be converted to:

$(\cdot \rightarrow NOT,\cdot \rightarrow NOT)\rightarrow OR\rightarrow OUTPUT$

Doing this without thought can increase the circuit size exponentially. So, when you see two $NOT$ gates one after another - cancel both of them out. I guarantee you this will work, but I wont prove it to you (this is your task)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Im not sure I understand your proposal. I wanna increase the circuit size to 2s so that negation gates are only applied to the input. So, I thought of applying DeMorgan's laws backwards which will result in increasing the gates by 1 for example if you apply it to a conjuction or disjunction. Since the size of the circuit is $s$ that means there are $s$ gates so it follows that if this procedure needs to be applied to at most $s$ gates then the circuit size will increase by at most $s$, thus the resulting circuit can be at most of size $2s$. That's my thought process. $\endgroup$
    – Gaussbaby
    Commented May 28, 2021 at 7:40
  • $\begingroup$ The thought process you described ispretty much what I explained in this answer. Basically, you use De-Morgan's law to move the "NOT" backwards (from the output to the input), and in order to make sure you won't end up with an exponential number of NOT gates, just cancel every two NOT gates that come together. Beware! It is possible to apply De-Morgan's law more than once per gate. $\endgroup$
    – nir shahar
    Commented May 28, 2021 at 9:45

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.