boolean formula
a boolean formula is a boolean circuit in which every vertex has a fan-out of 1 at most.
if not stated otherwise, by a formula we mean a DeMorgan formula, that is, a formula with fanin-2 AND and OR gates whose inputs are variables and their negations.
[cite:;taken from @complexity_jukna_2012 chapter 6 formulas]
[cite:;found in @computation_savage_1998 chapter 9.1.1 circuit models]
[cite:;found in @complexity_wegener_2009 chapter 1.4 circuits with bounded fan-out; definition 4.1]
given a formula we may also bound the fan-out of the inputs by 1 by using many copies of the inputs.
if not stated otherwise, by a formula we mean a DeMorgan formula, that is, a formula with fanin-2 AND and OR gates whose inputs are variables and their negations.
[cite:;taken from @complexity_jukna_2012 chapter 6 formulas]
[cite:;found in @computation_savage_1998 chapter 9.1.1 circuit models]
[cite:;found in @complexity_wegener_2009 chapter 1.4 circuits with bounded fan-out; definition 4.1]
the we denote by 
the minimal depth of a demorgan formula computing a given boolean function 
.
the minimal depth of a demorgan formula computing a given boolean function .since the underlying graph of a demorgan formula is a binary tree (broken link: blk:fig-bool-formula-1), any formula of depth 
can have at most 
leaves. this implies that, for every boolean function ,
broken link: xopp-figure:/home/mahmooz/brain/pen/1733210518.388299.xopp
[cite:;taken from @complexity_jukna_2012 chapter 6 formulas]
can have at most leaves. this implies that, for every boolean function ,broken link: xopp-figure:/home/mahmooz/brain/pen/1733210518.388299.xopp[cite:;taken from @complexity_jukna_2012 chapter 6 formulas]
the size of a boolean formula is the number of input gates it has.
a formula is minimal if no smaller formula computes the same function.
let 
, we denote by 
the function we receive by randomly setting a variable of to some random bit, then
[cite:;taken from @complexity_jukna_2012 lemma 6.8]
, we denote by the function we receive by randomly setting a variable of to some random bit, then[cite:;taken from @complexity_jukna_2012 lemma 6.8]let 
be a minimal DeMorgan formula which computes 
and has 
leaves (input gates). since has only 
variables, at least one variable 
must appear at least 
times as a leaf, that is, at least leaves are labeled by or 
. thus if we set to a constant 
, what we obtain is a formula of 
variables with at most 
leaves. but this is not the whole truth: when setting a variable to a constant we can expect to "kill off" not only the variable itself but also some other leaves labeled by other variables. to show this, say that a subformula 
of is a neighbor of a leaf 
, if 
or 
is a subformula of .
which appears 
times as a leaf of . let 
be the leaves labeled by or 
. by boolean_formula.html, for every 
there is a constant 
such that, after setting 
the neighbor 
of 
will disappear from , thereby erasing at least one more leaf which is not among the leaves . let be the constant which appears most often in the sequence 
. if we set 
, then all the leaves will disappear from the formula, and at least 
additional leaves will disappear because of these secondary effects. in total, we thus eliminate at least 
leaves, and the resulting formula has at most
leaves, as claimed. (the latter inequality is because in calculus we have 
, by bernoullis inequality).
[cite:;taken from @complexity_jukna_2012 lemma 6.8]
be a minimal DeMorgan formula which computes and has leaves (input gates). since has only variables, at least one variable must appear at least times as a leaf, that is, at least leaves are labeled by or . thus if we set to a constant , what we obtain is a formula of variables with at most leaves. but this is not the whole truth: when setting a variable to a constant we can expect to "kill off" not only the variable itself but also some other leaves labeled by other variables. to show this, say that a subformula of is a neighbor of a leaf , if or is a subformula of .if 
is a leaf of , then the neighbor of does not contain the variable .
is a leaf of , then the neighbor of does not contain the variable .let be a minimal non-constant formula, 
one of its leaves, and the neighbor of in . hence, 
(or 
) is a subformula of . for the sake of contradiction, assume that contains a leaf 
. replace this leaf by that constant for which the literal gets value 1. that is, replace the leaf by 1 if 
, and by 0 if 
(if 
then we set 
so that the literal gets value 0).
after this setting, the resulting subformula
has one leaf fewer than , but the resulting subformula 
computes the same boolean function as 
. to see this, take an input vector 
. if 
then 
and 
implying that 
. if 
then 
and we again have that 
. thus, we obtained a formula 
which computes the same boolean function as the original formula but has one leaf fewer. this contradicts the minimality of .
take now a variable be a minimal non-constant formula, one of its leaves, and the neighbor of in . hence, (or ) is a subformula of . for the sake of contradiction, assume that contains a leaf . replace this leaf by that constant for which the literal gets value 1. that is, replace the leaf by 1 if , and by 0 if (if then we set so that the literal gets value 0).after this setting, the resulting subformula
has one leaf fewer than , but the resulting subformula computes the same boolean function as . to see this, take an input vector . if then and implying that . if then and we again have that . thus, we obtained a formula which computes the same boolean function as the original formula but has one leaf fewer. this contradicts the minimality of . which appears times as a leaf of . let be the leaves labeled by or . by boolean_formula.html, for every there is a constant such that, after setting the neighbor of will disappear from , thereby erasing at least one more leaf which is not among the leaves . let be the constant which appears most often in the sequence . if we set , then all the leaves will disappear from the formula, and at least additional leaves will disappear because of these secondary effects. in total, we thus eliminate at least leaves, and the resulting formula has at mostleaves, as claimed. (the latter inequality is because in calculus we have , by bernoullis inequality).[cite:;taken from @complexity_jukna_2012 lemma 6.8]
let , we denote by the function we receive by choosing by random 
variables for 
, and setting them to random bits, then:
[cite:;taken from @complexity_jukna_2012 theorem 6.10]
, we denote by the function we receive by choosing by random variables for , and setting them to random bits, then:[cite:;taken from @complexity_jukna_2012 theorem 6.10]let . by applying broken link: blk:lem-bool-func-2 times, we obtain a formula of 
variables with at most
[cite:;taken from @complexity_jukna_2012 theorem 6.10]
. by applying broken link: blk:lem-bool-func-2 times, we obtain a formula of variables with at most- the equality can be shown through algebraic juggling:
[cite:;taken from @complexity_jukna_2012 theorem 6.10]
a better lower bound is achieved in boolean_formula.html.[cite:;taken from @complexity_jukna_2012 example 6.11]
if we fix all but one variables of 
, we obtain a boolean function (a variable or its negation) requiring formula of leafsize 1. thus, we can apply subbotovskaya's theorem 2 with 
and obtain that
which gives us
which gives us the lower bound 
. now we know that the circuit of forms a binary tree therefore
[cite:;found in from @complexity_jukna_2012 example 6.11]
, we obtain a boolean function (a variable or its negation) requiring formula of leafsize 1. thus, we can apply subbotovskaya's theorem 2 with and obtain thatwhich gives uswhich gives us the lower bound . now we know that the circuit of forms a binary tree therefore[cite:;found in from @complexity_jukna_2012 example 6.11]for 
:
:let 
be boolean variables, a restriction is a function 
, which we sometimes consider a broken link: blk:def-str in 
. given a function 
, we denote by 
the function received from such that for every variable where we have 
we replace by 
.
be boolean variables, a restriction is a function , which we sometimes consider a broken link: blk:def-str in . given a function , we denote by the function received from such that for every variable where we have we replace by .suppose that 
is a real number between 0 and 1. a -random restriction 
assigns each variable a value in 
, independently with probabilities
and
[cite:;variant of @complexity_jukna_2012 chapter 12 large-depth circuits]
the following theorem is actually the same as subbotovskaya's theorem 2.
is a real number between 0 and 1. a -random restriction assigns each variable a value in , independently with probabilitiesand[cite:;variant of @complexity_jukna_2012 chapter 12 large-depth circuits]let be a random restriction received by choosing variables at random and setting them to random bits, then for every we have:
[cite:;taken from @complexity_jukna_2012 lemma 6.12]
be a random restriction received by choosing variables at random and setting them to random bits, then for every we have:[cite:;taken from @complexity_jukna_2012 lemma 6.12]let , let be a -random restriction, then
[cite:;taken from @complexity_jukna_2012 theorem 6.13]
, let be a -random restriction, then[cite:;taken from @complexity_jukna_2012 theorem 6.13]
stated differently, 
.[cite:;taken from @complexity_jukna_2012 theorem 6.28]
given , we fix all but one variable, this can be the expected outcome of a random substitution with probability 
, and gives such that us 
hence
, we fix all but one variable, this can be the expected outcome of a random substitution with probability , and gives such that us hencefor every 
, almost for every function 
, we have:
BROKEN
, almost for every function , we have:BROKENhere 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.every dnf formula that computes has to contain terms, and the same argument is true for cnf.
has to contain terms, and the same argument is true for cnf.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.every function can be computed by a dnf formula of at most 
terms and the same argument is true for cnf formulas.
can be computed by a dnf formula of at most terms and the same argument is true for cnf formulas.