circuit complexity course homework 2
with a single output can be turned into a 
.
.proof for the first statement: for any gate 
at depth 
with outdegree 
we create 
instances of the subcircuit whose output gate is , from each new duplicate of we make an outgoing connection to the descendants of in the original circuit to receive a new circuit of the same depth but a different size. this is demonstrated in broken link: blk:fig-circ-comp-homework2-1.
broken link: xopp-figure:/home/mahmooz/brain/pen/1736627553.3050792.xopp
proof for the second and third statements:
at depth with outdegree we create instances of the subcircuit whose output gate is , from each new duplicate of we make an outgoing connection to the descendants of in the original circuit to receive a new circuit of the same depth but a different size. this is demonstrated in broken link: blk:fig-circ-comp-homework2-1.broken link: xopp-figure:/home/mahmooz/brain/pen/1736627553.3050792.xopp
proof for the second and third statements:
because formulas have bounded fan in, they form binary trees, and if we start at the bottom and iterate layer by layer to the top, eliminating half of the nodes at each step, we would have 
which means that 
.
this also means that
which means that .this also means that
- prove that in every binary tree
, there exists a vertex 
such that every subtree of contains atleast 
of the leaves of and not more than 
of the leaves of . - let
be a formula, let 
be a gate of , and let 
be the formula rooted in the gate . let 
be the formula received from by exchanging for the constant 0, we define the formula 
in a similar manner. prove that for every input 
we have
- prove that for every function 
we have
proof for the first statement:
can be a part of an implicant of 
or could have its own implicants which are also implicants of .
we start at the top (at the root of the tree) and jump down, each time jumping to the next significant child node, where "significant" means the one with atleast half the leaves of the current node, and there has to be such a child because its a binary tree.
on each jump we eliminate at most half of the leaves of the subtree rooted at the current node, this can be formulated as the following recurrence relation:
where 
. which means:
we ignore trees that have one leaf, we also may not be eliminating any leaves by jumping down but taking that into account isnt necessary as we could define jumping by finding the next proper descendant that has less than 
but more than 
of the nodes.
formulating it as a recurrence relation is somewhat unnecessary. the proof is really simple, since we're cutting at most half our leaves every time, and we start with
leaves and go down, we will get to 0 leaves if we keep going, but at some point before that we will have to cross from 
to 
, and at that point in time we will only be able to cut at most 
of the leaves where 
, so that jump cant be to a node that has less than 
leaves, we have to land in a point between and giving us the desired node.
for the second statement we need to consider that on each jump we eliminate at most half of the leaves of the subtree rooted at the current node, this can be formulated as the following recurrence relation:
where . which means:we ignore trees that have one leaf, we also may not be eliminating any leaves by jumping down but taking that into account isnt necessary as we could define jumping by finding the next proper descendant that has less than but more than of the nodes.formulating it as a recurrence relation is somewhat unnecessary. the proof is really simple, since we're cutting at most half our leaves every time, and we start with
leaves and go down, we will get to 0 leaves if we keep going, but at some point before that we will have to cross from to , and at that point in time we will only be able to cut at most of the leaves where , so that jump cant be to a node that has less than leaves, we have to land in a point between and giving us the desired node. can be a part of an implicant of or could have its own implicants which are also implicants of .we refer to gates and functions alike here.
if none of's implicants are implicants of then it trivially follows because doesnt affect the output anyway and the expression 
will always equal 
when 
is a constant that is 0 or 1 because we have 
and the whole expression reduces to one of 
or 
when 
or 
respectively, which both equal .
assume has multiple implicants that are also implicants of , when 
, we have that 
iff another implicant in that isnt in had the value 1, which also implies 
, hence the expression 
, which outputs 1 only such an implicant that isnt in is satisfied. when 
we necessarily have because atleast one of the implicants of is satisfied, in which case 
anyway because the implicant corresponding to was set to the constant 1. the expression 
reflects returns 1 only if this holds.
if none of
's implicants are implicants of then it trivially follows because doesnt affect the output anyway and the expression will always equal when is a constant that is 0 or 1 because we have and the whole expression reduces to one of or when or respectively, which both equal .assume
has multiple implicants that are also implicants of , when , we have that iff another implicant in that isnt in had the value 1, which also implies , hence the expression , which outputs 1 only such an implicant that isnt in is satisfied. when we necessarily have because atleast one of the implicants of is satisfied, in which case anyway because the implicant corresponding to was set to the constant 1. the expression reflects returns 1 only if this holds.let 
be a monotone function. prove that for every input 
we have 
iff 
satisfies some prime implicant of .
be a monotone function. prove that for every input we have iff satisfies some prime implicant of .if satisfies no 
, then 
couldnt be equal to 1, because each implicant 
isnt satisfied (if no prime implicant is satisfied, then no implicant is satisfied), so its value is 0, and 
.
satisfies no , then couldnt be equal to 1, because each implicant isnt satisfied (if no prime implicant is satisfied, then no implicant is satisfied), so its value is 0, and .in boolean_matrix_product.html we used the following claim: if is a bottleneck, then it has an implicant of the form 
for 
. in this problem we prove a more general version of this claim that demonstrates the general idea: in a boolean circuit, we can without loss of generality assume that for every internal gate we have an implicant that is contained in a prime implicant of an output gate.
prove the following claim: let
be a monotone function, let 
be a monotone circuit that computes , and let be a gate of . if we cant replace with 0 without changing the function that computes, then has an implicant that is contained in a prime implicant of .
is a bottleneck, then it has an implicant of the form for . in this problem we prove a more general version of this claim that demonstrates the general idea: in a boolean circuit, we can without loss of generality assume that for every internal gate we have an implicant that is contained in a prime implicant of an output gate.prove the following claim: let
be a monotone function, let be a monotone circuit that computes , and let be a gate of . if we cant replace with 0 without changing the function that computes, then has an implicant that is contained in a prime implicant of .let 
where 
, if we can replace with 0 without affecting then either no is part of any implicant of or for every there is some other gate that computes every and provides it to other nodes while computes it and disposes of it, which renders useless and a degenerated boolean function. contradictory to the assumption of nondegeneracy in complexity analysis.
where , if we can replace with 0 without affecting then either no is part of any implicant of or for every there is some other gate that computes every and provides it to other nodes while computes it and disposes of it, which renders useless and a degenerated boolean function. contradictory to the assumption of nondegeneracy in complexity analysis.let 
such that 
, we denote by 
the functions such that
let such that , we denote by the functions such that- for every 2 input variables
of , has atleast 3 distinct subfunctions that can be obtained by replacing 
with constants. - if
, then for every there exists some constant 
, such that we can set 
, we get a function in 
.
such that . prove that 
then 
, even if we allow the use of XOR gates.