circuit complexity course homework 3
prove that 
and 
.
and .for an upper bound we can simply analyze how the formula for the parity generalizes to 
variables and find the number of leaves for the trivial circuit construction of the formula. we have for the base case 
that 
, which requires 4 leaves for the 2 variables 
.
we construct the binary tree using the following property:
the construction shown in broken link: blk:pgs-circ-comp-hw3-1.
broken link: xopp-pages:/home/mahmooz/brain/pen/2025-01-26-Note-23-41.xopp
this construction gives us the following formulas:
by induction we get the recurrence relation
by the master theorem this gives us a complexity of
to show that the bound isnt restricted to even , we can note that for any 
we have 
.
a lower bound cannot be proved by a construction, we provide the following proof.
variables and find the number of leaves for the trivial circuit construction of the formula. we have for the base case that , which requires 4 leaves for the 2 variables .we construct the binary tree using the following property:
the construction shown in broken link: blk:pgs-circ-comp-hw3-1.broken link: xopp-pages:/home/mahmooz/brain/pen/2025-01-26-Note-23-41.xopp
this construction gives us the following formulas:
by induction we get the recurrence relation
by the master theorem this gives us a complexity ofto show that the bound isnt restricted to even , we can note that for any we have .a lower bound cannot be proved by a construction, we provide the following proof.
the relevant differing expression, 
, results from 
because we have 
. in order to bring 
down to 
we would need 
because
however, we cannot modify 
directly, but the expression is a result of 
, which means that if we get 
we would be done. by manipulating the expression, we get that this is achieved by
, results from because we have . in order to bring down to we would need becausehowever, we cannot modify directly, but the expression is a result of , which means that if we get we would be done. by manipulating the expression, we get that this is achieved bydenote by 
the OR function for bits.
the OR function for bits.- prove that for every function
we have
- we define the variation 
of the andreev's function by replacing the usage of 
with 
. prove
(with a better choice of 
we can improve it to 
).
yet to prove the first part
this problem is similar to andreevs_function.html.
we have
by boolean_formula.html there exists 
such that 
, fix to some function using an assignment 
, we get
and then
we have
by boolean_formula.html there exists such that , fix to some function using an assignment , we getand thenwe showed that every boolean function can be computed by a boolean circuit of size 
.
.- show that we can construct the circuit using
. - show that we can compute every function using
.
- this is the same as the proof for boolean_circuit.html, the proof uses an -DNF to construct the expression for the circuit.
- this is trivial by considering truth tables and then extracting minterms or maxterms.
prove that for every 
, we have an AC circuit with depth 
and size 
that computes 
. a lower bound for such circuits is given in ac_class.html, here we need to show an upper bound (by demonstrating a construction).
, we have an AC circuit with depth and size that computes . a lower bound for such circuits is given in ac_class.html, here we need to show an upper bound (by demonstrating a construction).for 
this is trivial, the construction is done by creating the circuit described in boolean_circuit.html for each -length string that should be accepted by 
, each such string would only need one AND gate (because we have unbounded fanin), and we have at most 
such strings (actually for parity it can be shown by be 
by counting strings with odd counts of 1), so we need AND gates, which would then be connected by a final OR gate at the output layer.
we build subcircuits that compute parity for a subset of the input with a depth of
and then "connect" them at the second-to-last layer using an OR gate, this gives us a circuit of depth . for 
, we slice the input into 
blocks, and then build upon each a circuit that computes 
with depth 
and we already showed that this can be done with size 
, and since we have 
such subcircuits, we will need to handle their output gates, again we do this with the trivial construction of size , and this amounts to 
.
although we get a bound on size of
for depth .
[cite:;variant of @complexity_jukna_2012 theorem 11.3]
this is trivial, the construction is done by creating the circuit described in boolean_circuit.html for each -length string that should be accepted by , each such string would only need one AND gate (because we have unbounded fanin), and we have at most such strings (actually for parity it can be shown by be by counting strings with odd counts of 1), so we need AND gates, which would then be connected by a final OR gate at the output layer.we build subcircuits that compute parity for a subset of the input with a depth of
and then "connect" them at the second-to-last layer using an OR gate, this gives us a circuit of depth . for , we slice the input into blocks, and then build upon each a circuit that computes with depth and we already showed that this can be done with size , and since we have such subcircuits, we will need to handle their output gates, again we do this with the trivial construction of size , and this amounts to .although we get a bound on size of
for depth .[cite:;variant of @complexity_jukna_2012 theorem 11.3]
- prove that if a DNF formula computes , then all of its terms have to be of width , show that this is also true for CNF and clauses aswell.
- prove that every DNF/CNF formula that computes has to be of size atleast .
here i show the proof for DNF's, the proof for CNF's and clauses should be similar (we can also use demorgan to show a bijection between DNF's and CNF's and the rest would follow).
the idea is to pick a string of length
that is less than that would be accepted by term of width of 
, but then extend the string to length and choose the other 
bits in a way that deliberately assures that the string shouldnt be accepted by but show that it still satisfies the term of width , to receive the desired contradiction disproving the statement. this happens because when considering terms of width less than it becomes infeasible to check whether we have an odd number of 1's in the input.
assume in contradiction that there is some DNF formula with a term of width 
and assume without loss of generality that is odd (the proof for an even is symmetric), let 
be a string of bits of width corresponding to the signs of the literals of the term , i.e. if 
is a negation of some literal we have 
and 
otherwise, this ensures that the term accepts the string 
because contains an odd number of 1's. now consider 
which is a string of length whose postfix is and let its prefix 
be all 0's except one bit, we get that 
is a string that contains an even number of 1's, and which shouldnt be accepted by , but it satisfies the term (and it only takes satisfying one term of a DNF to satisfy the whole formula), giving us a contradiction.
the idea is to pick a string of length
that is less than that would be accepted by term of width of , but then extend the string to length and choose the other bits in a way that deliberately assures that the string shouldnt be accepted by but show that it still satisfies the term of width , to receive the desired contradiction disproving the statement. this happens because when considering terms of width less than it becomes infeasible to check whether we have an odd number of 1's in the input.assume in contradiction that there is some DNF formula with a term
of width and assume without loss of generality that is odd (the proof for an even is symmetric), let be a string of bits of width corresponding to the signs of the literals of the term , i.e. if is a negation of some literal we have and otherwise, this ensures that the term accepts the string because contains an odd number of 1's. now consider which is a string of length whose postfix is and let its prefix be all 0's except one bit, we get that is a string that contains an even number of 1's, and which shouldnt be accepted by , but it satisfies the term (and it only takes satisfying one term of a DNF to satisfy the whole formula), giving us a contradiction.the total number of possible strings over 
with an odd number of 1's is , by the previous proof, we know we need to have atleast one term for each such possible string.
with an odd number of 1's is , by the previous proof, we know we need to have atleast one term for each such possible string.in class we proved that if there exists an 
circuit of size 
and depth that computes , then there exists a circuit of depth of standard form that computes it. but we ignored many details. write the complete proof, including the division of the circuit into layers.
circuit of size and depth that computes , then there exists a circuit of depth of standard form that computes it. but we ignored many details. write the complete proof, including the division of the circuit into layers.let 
be a function. prove that if every prime implicant is of size at most , then is computable by an -DNF.
be a function. prove that if every prime implicant is of size at most , then is computable by an -DNF.when we proved the switching lemma in class, we denoted 
and defined 
to be the set of assignments 
such that 
isnt computable by an -DNF. we then proved the claim that there exists some injective function from to 
. prove that this claim implies the switching lemma.
and defined to be the set of assignments such that isnt computable by an -DNF. we then proved the claim that there exists some injective function from to . prove that this claim implies the switching lemma.