parity function
[cite:;taken from @complexity_vollmer_1999 corollary 3.4]for every 
we have 
and 
.
the minimal number of AND and OR gates in a circuit over
computing 
is 
.
[cite:;taken from @complexity_jukna_2012 theorem 1.29]
[cite:;refer to @complexity_vollmer_1999 chapter 3.1.2 a lower bound for the parity function]
we have and .the minimal number of AND and OR gates in a circuit over
computing is .[cite:;taken from @complexity_jukna_2012 theorem 1.29]
[cite:;refer to @complexity_vollmer_1999 chapter 3.1.2 a lower bound for the parity function]
we use the elimination method.
by
we may denote the 
'th input of the circuit or its negation, we dont consider negated literals.
the upper bound follows since
is equal to 
. for the lower bound we prove the existence of some whose replacement by a suitable constant eliminates 3 gates. this implies the assertion for 
directly and for 
by induction.
let
be the first gate of an optimal circuit for 
, its inputs are different variables and 
. has to be an 
gate, otherwise we would have that the boolean formula of the circuit is one of 
which cannot be a parity formula because its value depends on 
. one property of the parity function is that it is non-degenerated, as in, it depends on all of its variables, so given the function , if we set some variable (namely ) to a constant, we should still be able to compute the function 
with a subset of the resulting circuit graph. bearing this property in mind, if had fanout 1, that is, if were the only gate for which is acting as input, then if we replace by the constant 0, the gate would also become a constant because 
. this would imply that the output became independent of the -th variable in contradiction to the non-degenerated property of parity (we wont be able to compute because we lost context of along with ). hence, must have fanout at least 2. this is demonstrated in broken link: blk:fig-parity-1.
we mentioned that has to be an gate, but even if it were an 
gate, the proof is symmetric except that we use the constant 1 to replace , as then would become redundant because 
.
broken link: xopp-figure:/home/mahmooz/brain/pen/1736510140.7040043.xopp
let
be the other gate to which is an input. we now replace by such a constant that becomes replaced by a constant (1 in the case of OR, 0 in the case of AND). since under this setting of the parity is not replaced by a constant, the gate cannot be an output gate. let 
be a successor of . we only have two possibilities: either coincides with (that is, has no other successors besides ) or not.
case (a):
. then we can set to a constant so that will become set to a constant. this will eliminate the need for all three gates 
and . this is because if was the constant 0 and was an OR gate, then is useless and it simplifies to the other input variable, if was the constant 1 and was an OR gate, again would become useless as it just becomes the constant 0. if was the constant 0 and was an AND gate, then again simplifies to 0, if was the constant 0 and was an OR gate, then simplifies to its other input variable, again rendering redundant, in any case can be eliminated. the cases for are symmetric for the two possible values of and the two possible functions for .
case (b):
. in this case has fanout 1. we can set to a constant so that will become set to a constant. this will eliminate the need for all three gates and 
.
in either case we eliminate at least 3 gates, this is demonstrated in broken link: blk:fig-parity-2.
broken link: xopp-figure:/home/mahmooz/brain/pen/1736546914.3335242.xopp
[cite:;taken from @complexity_jukna_2012 theorem 1.29]
by
we may denote the 'th input of the circuit or its negation, we dont consider negated literals.the upper bound follows since
is equal to . for the lower bound we prove the existence of some whose replacement by a suitable constant eliminates 3 gates. this implies the assertion for directly and for by induction.let
be the first gate of an optimal circuit for , its inputs are different variables and . has to be an gate, otherwise we would have that the boolean formula of the circuit is one of which cannot be a parity formula because its value depends on . one property of the parity function is that it is non-degenerated, as in, it depends on all of its variables, so given the function , if we set some variable (namely ) to a constant, we should still be able to compute the function with a subset of the resulting circuit graph. bearing this property in mind, if had fanout 1, that is, if were the only gate for which is acting as input, then if we replace by the constant 0, the gate would also become a constant because . this would imply that the output became independent of the -th variable in contradiction to the non-degenerated property of parity (we wont be able to compute because we lost context of along with ). hence, must have fanout at least 2. this is demonstrated in broken link: blk:fig-parity-1.we mentioned that
has to be an gate, but even if it were an gate, the proof is symmetric except that we use the constant 1 to replace , as then would become redundant because .broken link: xopp-figure:/home/mahmooz/brain/pen/1736510140.7040043.xopp
let
be the other gate to which is an input. we now replace by such a constant that becomes replaced by a constant (1 in the case of OR, 0 in the case of AND). since under this setting of the parity is not replaced by a constant, the gate cannot be an output gate. let be a successor of . we only have two possibilities: either coincides with (that is, has no other successors besides ) or not.case (a):
. then we can set to a constant so that will become set to a constant. this will eliminate the need for all three gates and . this is because if was the constant 0 and was an OR gate, then is useless and it simplifies to the other input variable, if was the constant 1 and was an OR gate, again would become useless as it just becomes the constant 0. if was the constant 0 and was an AND gate, then again simplifies to 0, if was the constant 0 and was an OR gate, then simplifies to its other input variable, again rendering redundant, in any case can be eliminated. the cases for are symmetric for the two possible values of and the two possible functions for .case (b):
. in this case has fanout 1. we can set to a constant so that will become set to a constant. this will eliminate the need for all three gates and .in either case we eliminate at least 3 gates, this is demonstrated in broken link: blk:fig-parity-2.
broken link: xopp-figure:/home/mahmooz/brain/pen/1736546914.3335242.xopp
[cite:;taken from @complexity_jukna_2012 theorem 1.29]