noc21-cs49-lec24

So, then so, what we so, the idea behind showing this lemma was that we wanted to prove Valiant Vazirani's theorem. So, let me state that theorem once again, but before stating that let me just define this language. So, that it will be little easier to state that theorem. So, define this language u sat to be set of all formulas Boolean formulas let us say in c n f form all Boolean formulas phi such that has exactly 1 satisfying assignment. So, now, we can restate Valiant Vazirani's theorem in this context that there exist a probabilistic polynomial time machine m such that given any Boolean formula phi let us say over n variables if phi is satisfiable then the probability that m given phi belongs to u sat is greater than or equal to 1 over 8 n and if phi is unsatisfiable then the probability that m given phi. So, I will make this a little bit more stronger belongs to sat is 0. So, it is not even satisfiable the new formula that we construct. So, this is just a rephrasing of the theorem that we stated at the beginning of last class. So, what we said was that if phi is unsatisfiable the new formula that we construct is not satisfiable and if phi were to be satisfiable then the new formula has a unique satisfying assignment with at least so much probability. So, how does this follow from the lemma that we have. Yeah. So, basically the way we are defining this language u sat. So, the way in which complexity theorists look at this language u sat is they think of this as a promise problem. So, it is not exactly a language or it is not exactly a problem in the traditional sense in the sense that every string which belongs to the language has this property and every string which does not have the properties outside this language. It is not exactly that it is basically you have this set let us say. So, I just defer this proof. So, we have this set let us say 0 1 star or 0 1 to the power n and you divide this into 2 sets set of all some y and there is another disjoint set which I call n. So, now we say that an instance belong to u sat if it belongs to the y partition and it belongs it does not belong to u sat if it belongs to the no partition. So, in this case our no will be set of unsatisfiable assignments and y is the set of assignments with exactly 1 y is the set of Boolean formulas with exactly 1 satisfying assignment because. . Exactly. So, the here we have the promise that the input belongs to only the union of these 2 things, but clearly there can be other formulas which lie outside which have let us say 2 satisfying assignments or things like that. So, that is why I stated this as belonging to sat instead of u sat. So, these are known as promise problems in complexity, but how do we prove this? So, the proof is not difficult basically what you do is you construct a formulas xi as follows. So, you first randomly pick k from the following set 0 up to n minus 1 and then randomly pick a 1 how many do we need k plus 2 a 1 through a k plus 2 in 0 1 to the power n k such vectors and also you pick these bits b 1 through b k plus 2 and construct the formula let us call it xi as follows. So, xi of x is defined as it is the conjunction of the input formula phi x with the following clauses. So, the first clause is a 1 dot x plus b 1 is equal to 0. So, it is basically the same way as this hash function works if you just look at this entire thing that we have here this is nothing, but saying that h of x is equal to 0 to the power k plus 2 right you have. So, I am just splitting that into these k plus 2 clauses and you can always come up with Boolean expressions with and or and not gates which will be equivalent to these whatever these clause states and then we can just apply the earlier lemma. So, the earlier lemma says that for some k such that the cardinality of t lies between 2 to the power k and 2 to the power k plus 1 the probability that the number of x is that gets hashed to the all 0 string is 1 is at least 1 over 8. So, therefore, the probability that xi of x is in u sat is equal to the probability that yeah. So, I do not want to write this entire thing, but basically it is equal to that there exist a k such that this formula phi of x conjunction with this h of x equal to 0 to the power k plus 2. So, this belongs to u sat and if you just apply the union bound here this is greater than 1 over 8 times 1 over n because the probability that the correct k is chosen is 1 over n. So, 1 immediate corollary of this result is that if there exist a polynomial time machine m that given a Boolean formula phi with exactly 1 satisfying assignment output set then N p is equal to R p. So, we know that R p is contained in N p, but suppose if you have a deterministic polynomial time machine which does the following. So, suppose if the machine is given a formula phi which does not have this property then we do not assume any we do not assume anything about the machine. So, it can do anything, but if it is given a formula which has this property that it is it has only 1 satisfying assignment then the machine will output it. So, the proof is again simple. So, suppose if you have such a machine what you do is given a formula phi what you do is first you generate all this different xi's. So, you are. So, the idea is that for all k construct xi 1 up to or xi 0. So, we are taking k in 0 up to N minus 1. So, you construct these formulas xi 0 to xi N minus 1 and then you feed it to this polynomial time machine. So, we know from the earlier thing that there is 1 which has I mean. So, 1 of these formulas have a unique satisfying assignment with high probability if the given formula phi were to be satisfiable. So, the polynomial time machine outputs that formula and that will help us to check whether phi is satisfiable or not yeah. So, the you can check the details, but. So, any questions? . No, but then you are strengthening the hypothesis right you are assuming a more powerful machine. I am only saying that if there exist even a polynomial time machine which is which has less power see R P machine has more power than a polynomial time machine right. . If it is an R P machine then it implies that it is. So, if we have this condition then it implies that M is also an R P machine basically which has 0 error right yeah you can say that also, but if we have a R P machine yeah it will work. So, any other questions? So, let us look at some definitions. So, we will look at some counting classes. So, in more generally we will look at what is known as counting complexity and we will try to come up with an analogous theorem of Valiant Vazirani's theorem. So, if phi is a Boolean formula define sharp phi to be equal to the number of satisfying assignments of phi and in the same way you can define this function sharp sat that given a formula phi it outputs the number of satisfying assignments of that formula. So, this is just the number it is not outputting all the assignments, but just the cardinality of that set. So, more generally we can define what is known as the class we just take this as a definition sharp p. So, this is not again a usual complexity class in the sense that this is not a class of languages per say, but it is a class of functions. So, sharp p is the class of functions f from 0 1 star to natural numbers let me just refresh this a little bit. A function f is said to be in sharp p if there exist a polynomial time machine m and let us say a polynomial p such that for all x f of x is the cardinality of the set of all strings y having size p of the length of x such that m given x and y accepts. So, in other words what is this class of functions it is in terms of the language n p it is the number of certificates. So, an equivalent way of looking at this definition is. So, f belongs to sharp p if there exist and n p machine n such that for all x f of x is the number of certificates of n on x if you simulate the machine n on x f of x is the number of certificates. So, it can be 0 also in particular when the string does not belong to the language of n number of certificates is 0 and that is the only time when it is 0. So, let me just state this result. So, this language or this function sharp sat. So, this is complete for sharp p and the proof of this is basically observing that the reduction cooks reduction that we saw earlier in this course is basically a reduction which preserves certificates. So, if you are given a language in n p and for every string the corresponding formula that you constructed that was basically a reduction which preserved certificates. So, whatever certificates that machine had for that string the corresponding Boolean formula will also have that same number of certificates. So, I would not again go into the details of that proof, but you can check it for yourself. So, I will just leave this as an exercise with the comment that cooks reduction is. So, the technical term for this property is that it is parsimonious in other words certificates are preserved. So, I think even in the book if you look at chapter 17 section 3 there is a short proof of this result. I mean again they do not give a proof I mean they just argue that why is cooks reduction parsimonious. You can look at the following section, but. So, let me come back to where we are. So, similar to the that sharp quantifier we can also define another quantifier. So, this is known as parity. So, parity of phi is equal to 1 if the Boolean formula phi has an odd number of satisfying assignments that is this is odd and it is equal to 0 otherwise. And again using this quantifier we get the language parity sat which is set of all formulas phi such that parity phi is equal to 1 all those Boolean formulas which have an odd number of satisfying assignment. So, now as an immediate corollary of Valiant Vazirani's theorem we get the following result that there exist a probabilistic polynomial time machine M such that for all Boolean formulas phi if phi is satisfiable then the probability that M of phi belongs to parity sat is greater than 1 over 8 n. And if phi is not satisfiable then the probability that M of phi is also not satisfiable has 1 probability I mean in the other words if M of phi satisfiable is has 0 probability. So, and this is again obviously, true because if M of phi belongs to U sat it means it has only 1 satisfying assignment which clearly means that it belongs to parity sat as well because it is odd. So, 1 is odd. So, that is the reason why this is true, but so yeah. So, this is something which seems very obviously, true and a question is that why are we going in this direction. So, the reason we are going in this direction is because we want to amplify this probability. So, let us look at. So, let us come back to Valiant Vazirani's theorem and let us ask the same question here that is it possible for us to amplify this probability that is given by Valiant and Vazirani. Can we do any better than 1 over 8 n? In other words suppose if a formula is satisfiable can I construct some formula xi which belongs to U sat with a value that is greater than 1 over 8 n. So, again last class we saw this argument as to how the success probability of a RP machine can be amplified. It is basically by taking some number of trials and you take the or of all those trials. I mean if one of those trials gives a positive answer you output a positive answer and then the probability that you do get a negative answer is 1 minus the product of all these things which is very small, but what happens here? I mean what happens if we try to simulate that same argument here. So, let us say that this is the formula xi that we get. So, when I run this machine once I get a formula xi. Now, suppose I want to amplify this probability and I run this machine a second time. Let us say I get a formula xi 1. Now, suppose that one of those formulas were to be true and the other is false can I claim that or can I construct a formula from xi and xi 1 which belongs to U sat. So, that is something which is not known to be true. In other words if you let us say you take some t trials of this machine m you run this some t times and you get some t formulas xi 1 up to xi t. How can you combine these formulas such that if the original formula were satisfiable the combination of all these t formulae gave you only one satisfying assignment. So, that is something which is I mean not known. In fact, so this it is an open problem whether any number that is better than 1 over 8 n can be achieved for this theorem. So, that is an open question. So, can we do better than 1 over 8 n. So, this is open in the context of the U sat version of Valiant and Vazirani. But as it turns out parity sat is much more expressive. Parity sat has much more power than U sat and we can go ahead and amplify this probability to any number which is exponentially close to 1. So, that is what we want to show. So, let us see why that is true. So, is it clear what we are trying to get here any questions. So, let us look at some properties of this quantifier parity. So, let phi and xi be 2 Boolean formulae over n and m variables respectively. Then what we can do is we can construct Boolean formulae whose I mean which have the following property. So, the first thing is that there exist if we look at the. So, the number of satisfying assignments of phi taken as a product with the number of satisfying assignments of xi is equal to the number of satisfying assignments of another Boolean formula phi dot xi where we define this phi dot xi. Let us say over the set of variables x comma y as phi of x and psi of y. So, let us just see what we are saying here. So, suppose if you have 2 Boolean formulae phi and xi over the set of variables x and y. So, think of x and y as a vector of variables. So, I can just write that here where x has n variables and y has m variables. Then if we consider the formula phi dot xi over the set of variables which is a concatenation of all the variables in x and y defined as the conjunction of these 2 formulae. Then the total number of satisfying assignments of this new formula is a product of the number of satisfying assignments of these 2 individual formula. So, this is easy to see because you take any satisfying assignment of phi and you take any satisfying assignment of psi and you just concatenate those 2 that will give you a satisfying assignment of phi dot psi. And similarly you take any satisfying assignment of phi dot xi and you just look at the appropriate partition. So, the individual bit strings will be satisfying assignments of these 2 individual formulae. So, also we can do a similar thing if you want the sum of the 2. So, suppose I want to define a formula let me call it. So, such that the number of satisfying assignments of phi plus the number of satisfying assignments of xi is equal to the number of satisfying assignments of this new formula which we denote as phi plus xi such that. So, this is what we want. So, how do we define this? So, will or work or will actually give much more. So, actually it will be. So, it will have some m times 2 to the power n plus n times 2 to the power n. So, what you want is just this plus this you want much lesser. So, or will not work. So, the way you can do it is there is a little tricky way to define this. So, before we go into this plus thing how many variables does this new formula have in terms of phi and xi. So, the number of variables of phi dot xi is m plus n. So, let us come here. So, phi plus xi. So, we define a new set of variables z as equal to. So, let us assume at m is less than n. So, it is the formula z naught equal to 0 and phi of z 1 up to z n or the clause z naught equal to 1 and z m plus 1 is equal to 0. So, on up to z n is equal to 0 and xi of z 1 up to z m. So, let us take a moment here and understand what is happening. So, we construct this formula phi plus xi. So, in this case it is a formula over n plus 1 variable. So, because we assume that n is greater than m, but in general basically the number of variables in phi plus xi would be the max of n comma m plus 1. So, here since we are assuming n is the larger number we have z as a over n variables. Yes. So, z m plus 1 and z m plus 2 and so on up to z n because m is smaller than n that is why. So, exactly what is happening here? So, let us understand the intuition behind this construction. So, what we want is that only if one of the. So, let us look at the 2 clauses that we have. So, this is one clause and this is the other clause. So, one property of this entire construction is that both these clauses cannot be true at the same time because one contains z naught equals 0 and the other contains z naught equals 1. So, only one of them can be true. Moreover let us say the first clause is true then it implies that phi is also true it has a satisfying assignment and if the second clause is true then it implies that xi is equal to true. So, if we take a satisfying assignment of phi that we can translate into a satisfying assignment of phi plus xi just by setting z naught equal to 0 and if we take a satisfying assignment of xi we can translate that into a satisfying assignment of phi plus xi again by setting z naught equal to 1 z m plus 1 equal to 0. So, 1 up to z n equal to 0 and whatever is the value that is therefore, z 1 to z m. So, note that these variables are exclusive. So, z naught only appears once here and then we have z 1 to z n and here again z 1 to z m does not appear in any of these equalities that is one direction. Similarly we can also look at the other direction that if phi plus xi has a satisfying assignment as we argued earlier that both these clauses simultaneously cannot be true. So, if this has a satisfying assignment then either z naught equal to 0 or z naught equals 1. So, if z naught equals 0 then it means that there is a satisfying assignment of phi as well and if z naught equals 1 it means that these clauses have I mean these variables z m plus 1 through z n all have a value 0 and there is a satisfying assignment for xi as well. So, you can see both directions. So, that is the essential idea, but I just leave it as an exercise to formally prove this. So, just go back and write out the proof. So, is this construction clear? So, now let me just state one more property and then we will leave it at that point I will state this as an observation. So, firstly, if you look at parity of phi and parity of xi. So, this is equal to parity of the formula phi dot xi. So, in other words if. So, when is the left side true or when does the left side evaluate to 1 when both these are odd when both these have an odd number of satisfying assignments. So, if both these have an odd number of satisfying assignment the product of two odd numbers is odd which means that this is also true and similarly the only way in which the product of two numbers can be odd is if both the numbers are odd which implies that this is also true and this is also true. So, that is easy to see the second property is that. So, basically what we are showing here is that this parity operation is or this parity quantifier is closed under the Boolean and operation. Similarly, it is also closed under the not operation. So, not of parity of phi is equal to parity of the following formula. So, I will call it phi plus 1 where phi plus 1 is some formula such that number of satisfying assignments of phi plus 1 is equal to number of satisfying assignments of phi plus 1. So, in other words you can take this formula to be xi where it is some trivial formula let us say x it has only one variable if it has only one variable then it has exactly one satisfying assignment which is 1. So, you can trivially construct a formula by applying this construction. So, now, why is this true because if this were to be true then now this becomes odd sorry even which makes this false and vice versa. The third one is a little bit tricky, but again not difficult to see is with respect to the or operation. So, phi parity phi or parity xi is equal to again parity of a single formula what do you think it should be. So, we want this to be true if at least one of them is true. So, you can use the not also by using De Morgan's law, but you can give a more direct formula. So, it is phi plus 1 product it is phi plus 1 dot xi plus 1 plus 1. So, if one of them is true. So, let us say this is true that means, this has an odd number. So, then this will have an even number. So, an even number product with any number is always even. So, this entire thing becomes odd and the only way this will become even is when both these numbers are odd which is when both these have an even number of satisfying assignment which means that both these are false. So, that is what I had. So, now, actually you can see yourself that you can try to see how this will help you to boost this probability, but anyway we will discuss it next time how these things can be used. So, anyway we have over shot we will stop here.