switching lemma
this is the version from class
let 
and let 
. let 
be a function computable by a \(k\)-cnf, and let 
be a p-random restriction that maintains 
variables "alive" and substitutes random bits with others, then the probability that we cant compute 
by an 
-dnf is at most 
.
[cite:;variant of @complexity_jukna_2012 lemma 12.1]
the following is a special case of the previous lemma. and let . let be a function computable by a \(k\)-cnf, and let be a p-random restriction that maintains variables "alive" and substitutes random bits with others, then the probability that we cant compute by an -dnf is at most .[cite:;variant of @complexity_jukna_2012 lemma 12.1]
let 
, let 
be a function that is computable by a 
-cnf, and let be a random restriction that maintains 
variables alive, then the probability that we cant compute by an -dnf is at most 
.
[cite:;variant of @complexity_jukna_2012 theorem 12.7]
, let be a function that is computable by a -cnf, and let be a random restriction that maintains variables alive, then the probability that we cant compute by an -dnf is at most .[cite:;variant of @complexity_jukna_2012 theorem 12.7]
let 
denote the length of the longest minterm of 
. let be a 
-CNF, and let be a \(p\)-random restriction. then 
.
[cite:;taken from @complexity_jukna_2012 chapter 12.1]
denote the length of the longest minterm of . let be a -CNF, and let be a \(p\)-random restriction. then .[cite:;taken from @complexity_jukna_2012 chapter 12.1]
we denote by 
be the set of all restrictions leaving exactly variables unassigned.
[cite:;found in @complexity_jukna_2012 chapter 6.3 the effect of random restrictions]
be the set of all restrictions leaving exactly variables unassigned.[cite:;found in @complexity_jukna_2012 chapter 6.3 the effect of random restrictions]
[cite:;taken form @complexity_jukna_2012 chapter 12.2]let and 
be integers such that 
, where 
is the total number of variables. let be the length of the longest minterm of , and let
in particular, 
contains all restrictions 
for which cannot be written as an \(s\)-dnf.
[cite:;taken from @complexity_jukna_2012 chapter 12.2]
and be integers such that , where is the total number of variables. let be the length of the longest minterm of , and letin particular, contains all restrictions for which cannot be written as an \(s\)-dnf.[cite:;taken from @complexity_jukna_2012 chapter 12.2]
the following lemmas are also duplicates from class
the following lemma entails the switching lemma.
.let 
as in the switching lemma, the probability that 
is a function that isnt a constant is at most 
.
as in the switching lemma, the probability that is a function that isnt a constant is at most .it is sufficient to prove that it is possible to encode any restriction 
by a pair 
.
by a pair .there exists some injective from 
to 
.
to .given two restrictions 
we denote by 
the restriction we get by substituting them together.
we denote by the restriction we get by substituting them together.if is a -cnf then
[cite:;taken from @complexity_jukna_2012 lemma 12.1]
is a -cnf then[cite:;taken from @complexity_jukna_2012 lemma 12.1]before giving the proof this lemma, we show that it indeed implies the switching lemma. to see this, take a random restriction in 
for 
, where is the total number of variables. then, by this lemma, for every 
, the probability that 
cannot be written as an -DNF is at most
in order to prove that some set 
cannot be very large, try to construct a mapping 
of to some set which is a priori known to be small, and give a way to retrieve each element 
from its code 
. then Code is injective, implying that 
.
let
be a -CNF formula for . fix an order of its clauses and fix an order of literals in each clause. we want to upper-bound the number 
of restrictions 
that are "bad" for , that is, for which the subfunction contains a minterm of length 
. our goal is to use the underlying CNF formula to construct an encoding
such that, knowing the formula , we can reconstruct a restriction from 
. by the coding principle, we will be then done.
to construct the desired encoding, fix a bad restriction
. we know that the subfunction must contain a minterm 
of length 
. by unspecifying an arbitrary subset of 
variables, we truncate to 
so that has length exactly . after is applied to , some clauses get the value 1 and disappear, while some literals get the value 0 and disappear from the remaining clauses. moreover, cannot set any clause to 0, for otherwise we would have 
. further, we have that 
cannot be constant because was a minterm of .
consider the first clause
of which is not set to 1 by but is set to 1 by 
. let 
be the portion of that assigns values to variables in . let also 
be the uniquely determined restriction which has the same support as and does not set the clause to 1. that is, evaluates all the literals "touched" by to 0.
define the string
based on the fixed ordering of the variables in clause by letting the 
-th component of 
be 1 if and only if the -th variable in is set by (and hence, also by ). that is, is just the characteristic vector of the (common) support of restrictions and . note that there must be at least one 1 in (the support of cannot be empty). Here is a typical example:
the main property of the string is that knowing and we can reconstruct : string tells us what literals of must be set by the restriction , and the property that does not evaluate to 1 allows us to infer the restriction itself.
now, if
, we repeat the above argument with 
in place of , 
in place of and find a clause 
which is the first clause not set to 1 by . based on this we generate 
, 
and 
as before. continuing in this way we get a sequence of clauses 
. each 
contains some variable that was not in 
for 
so we must stop after we have identified 
clauses. hence, 
.
let
be a vector that indicates for each variable set by (which are the same as those set by 
) whether it is set to the same value to which 
sets it. (recall that 
must set at least one literal of to 1 and may set some of them to 0, whereas 
sets all these literals to 0.) we encode the restriction by the string
our goal is to show that: (1) the mapping 
is injective, and (2) its range is not too large. to achieve the first goal, it is enough to show how to reconstruct uniquely, given .
first note that it is easy to reconstruct. identify the first clause of which is not set to 1 by 
. since none of the sets a clause to 1, this must be clause . now use to identify the variables of that are set by , and use 
to identify how would set these variables. thus we have reconstructed the sub-restrictions and . knowing these sub-restrictions and the entire restriction we can reconstruct the restriction 
.
now we can identify: it is the first clause of which is not set to 1 by . then we use to identify the variables of set by and use to identify how would set these variables. continuing in this way, we can reconstruct the restriction 
and thus the original restriction .
to finish the proof of the lemma, it is enough to upper-bound the range of the mapping Code. first, observe that restrictions belong to 
. hence, the number of such restrictions does not exceed 
. the number of strings is clearly at most 
. finally, each 
is a string in 
with the property that each substring 
has at least one 1 and the total number of 1s in all 
is . the number of such strings with 
ones in 
is
the number of positive integers 
such that 
is 
(show this!). thus the range of does not exceed 
as desired.
[cite:;taken from @complexity_jukna_2012 lemma 12.1]
in for , where is the total number of variables. then, by this lemma, for every , the probability that cannot be written as an -DNF is at mostin order to prove that some set cannot be very large, try to construct a mapping of to some set which is a priori known to be small, and give a way to retrieve each element from its code . then Code is injective, implying that .let
be a -CNF formula for . fix an order of its clauses and fix an order of literals in each clause. we want to upper-bound the number of restrictions that are "bad" for , that is, for which the subfunction contains a minterm of length . our goal is to use the underlying CNF formula to construct an encodingsuch that, knowing the formula , we can reconstruct a restriction from . by the coding principle, we will be then done.to construct the desired encoding, fix a bad restriction
. we know that the subfunction must contain a minterm of length . by unspecifying an arbitrary subset of variables, we truncate to so that has length exactly . after is applied to , some clauses get the value 1 and disappear, while some literals get the value 0 and disappear from the remaining clauses. moreover, cannot set any clause to 0, for otherwise we would have . further, we have that cannot be constant because was a minterm of .consider the first clause
of which is not set to 1 by but is set to 1 by . let be the portion of that assigns values to variables in . let also be the uniquely determined restriction which has the same support as and does not set the clause to 1. that is, evaluates all the literals "touched" by to 0.define the string
based on the fixed ordering of the variables in clause by letting the -th component of be 1 if and only if the -th variable in is set by (and hence, also by ). that is, is just the characteristic vector of the (common) support of restrictions and . note that there must be at least one 1 in (the support of cannot be empty). Here is a typical example:the main property of the string is that knowing and we can reconstruct : string tells us what literals of must be set by the restriction , and the property that does not evaluate to 1 allows us to infer the restriction itself.now, if
, we repeat the above argument with in place of , in place of and find a clause which is the first clause not set to 1 by . based on this we generate , and as before. continuing in this way we get a sequence of clauses . each contains some variable that was not in for so we must stop after we have identified clauses. hence, .let
be a vector that indicates for each variable set by (which are the same as those set by ) whether it is set to the same value to which sets it. (recall that must set at least one literal of to 1 and may set some of them to 0, whereas sets all these literals to 0.) we encode the restriction by the stringour goal is to show that: (1) the mapping is injective, and (2) its range is not too large. to achieve the first goal, it is enough to show how to reconstruct uniquely, given .first note that it is easy to reconstruct
. identify the first clause of which is not set to 1 by . since none of the sets a clause to 1, this must be clause . now use to identify the variables of that are set by , and use to identify how would set these variables. thus we have reconstructed the sub-restrictions and . knowing these sub-restrictions and the entire restriction we can reconstruct the restriction .now we can identify
: it is the first clause of which is not set to 1 by . then we use to identify the variables of set by and use to identify how would set these variables. continuing in this way, we can reconstruct the restriction and thus the original restriction .to finish the proof of the lemma, it is enough to upper-bound the range of the mapping Code. first, observe that restrictions
belong to . hence, the number of such restrictions does not exceed . the number of strings is clearly at most . finally, each is a string in with the property that each substring has at least one 1 and the total number of 1s in all is . the number of such strings with ones in isthe number of positive integers such that is (show this!). thus the range of does not exceed as desired.[cite:;taken from @complexity_jukna_2012 lemma 12.1]