noc21-cs49-lec10

[Music] [Music] okay so let's get started so last time we were discussing the polynomial hierarchy okay so i will get into the discussion in a few minutes but before that i just want to digress a little bit and talk about something else so we saw we talked about space bounded complexity classes ok and we saw the class p space so let us look at a complete problem for p space i wont prove the completeness part in our lecture but i will motivate as to why it is a complete problem and if you are interested in the proof you can always go back and read it its there in your text okay so we have seen what a boolean formula is and what does it mean to say that a boolean formula is satisfiable right so suppose we if we have a boolean formula phi we say it is satisfiable if there exist an assignment to the variables of that formula which makes the formula evaluate to true or one however you want to think of it so suppose so what we are saying is there exist an assignment to the variable suppose the formula has n variables what i am saying is that each of those variables can take a value 0 or 1. so instead of quantifying each variable with a existential quantifier i can generalize this idea and talk about variables which are bounded by the universal quantifier okay so instead of saying that a variable can take any value between 0 and 1 i say that well the formula has to be true for all possible values that the variable can take so whether it is 0 or 1 i do not care it has to evaluate to true okay i mean a very simple example is suppose if you look at the probably the most simplest formula let us say just a single variable x one so this formula i mean if you think of this as a formula this formula is always satisfiable right because if you set x one to one it gets evaluated to one but if i want this formula to be satisfiable for all possible values of x one then we see that phi is not satisfiable because if i assign zero to x one clearly it is not satisfiable so this is what is the distinction between these two ideas so let us try to encompass this idea into a formal definition so a quantified boolean formula which in short we will denote as qbf is of the form ok some q 1 x 1 so we will assume that the formula is formula in n variables q 2 x 2 so on till q n x n such that we have some formula phi on n variables where each qi is either a existential quantifier or a universal quantifier so when do we say that this formula evaluates to true if for the appropriate setting of the keyws for example if q1 is an existential quantifier then i allow x1 to take any value 0 or 1 okay for any setting of the value ah i'll consider the formula phi if q2 is an uh universal quantifier okay so then i want this formula to be satisfiable for all possible values of q x 2 that is whether it is 0 or 1 ok so this is what this is what i mean by a quantified boolean formula and the language tqbf okay so t stands for true is the set of all quantified boolean formulas let us call them psi such that psi is a qbf that evaluates to or i shouldn't say evaluates that is satisfiable foreign appropriate setting of the variables okay yeah i mean quantifiers are already fixed but depending on the quantifiers i am giving values to the variables that is what i mean here right so if it is a there exist even if it is an existential quantifier it can take any value and if it is a universal quantifier it should be true for all values that is what i mean universal quantifier 0 1 they are all boolean variables right so we are looking at boolean formulas so each x i can take values between 0 and 1 and we can also assume in addition that phi is a ah formula in ah three cnf so it's a conjunctive normal formula with three liters per clause so that does not make a difference okay so is this language clear to everybody so clearly we can see that this is a generalization of ah of the three sat language because if i set all my quantifiers to existential quantifier that will basically mean that this is nothing but just the language sat so the theorem is that t q b f is p space complete ok so i will just discuss the containment part that why is uq tqbf contained in p space in other words we need to give an algorithm so how do you give an algorithm for this language a p space ah p space algorithm ah right so yeah that is one way to look at it yeah so let us give a re recursive algorithm and you can also give an iterative algorithm but probably that will be more difficult to construct because ah it will be an exponential time algorithm so yeah so let us give a recursive algorithm so let me call this algorithm a okay which takes some qba formula phi and then tries to answer yes or no depending on whether phi is satisfiable or not so if n is equal to 0 that is it does if phi doesn't have any vary ah variables okay so we are also considering the special case when ah i mean a formula consists only of constants zeros and ones so it say and an or of constants in which case its easy to evaluated ok so then ah just output the value of whatever value you get by evaluating phi okay so it's just constants else that is if n is greater than 0 okay so if n is greater than 0 then we know that it has at least one variable so there is a quantifier associated with that variable if q1 is an existential quantifier what we do is we check the following two formulas we that is we check the formula 5 with x1 set i mean x1 getting the value zero so if a of psi with x1 set to 0 is equal to yeah we can just say that also because this is just some value so if this is 1 or a 5 x 1 is equal to 1 is 1 so either of these 2 return a 1 then we output 1 okay so now we again go back to this if else if q1 is a universal quantifier then we check if a phi x one is equal to zero is one and a phi x one is equal to one is also a one okay so it's a ah very standard uh intuitive algorithm so the point is how much space does this take so the thing again is that ah space can be reused so when i am computing ah phi okay and i am making recursive call to phi with x1 set as 0 and 5 with x1 set as 1 i can reuse the space in both these recursive calls okay so let us say that for a formula of size n and i am sorry a formula with n variables and of size m okay so so suppose phi has n variables psi and phi has size m then the space taken with n comma m as parameters is ah the space required for n minus 1 comma m okay plus some constant times m okay because we need this much amount of space to basically write out this expression on the tape and then run the algorithm on it because basically what we are doing in this algorithm is that we need to write out what the ah the new formula would be on which i am running my recursive calls so for that i need some constant times m space huh so basically if you look at one iteration how much space am i requiring here okay so to make a recursive call to a this is the amount of space i am requiring okay and the same space can be reused here also okay the only thing that i need to remember is what is the bit that this guy had output okay so that is the only thing that i need to remember but then i need to so to to be able to run a on a particular formula i need to know what that formula is right so that's why i am just assuming that i write out that particular formula on the tip and that requires some m space right yeah so yeah i guess you can make this some constant so yeah so you have this thing globally written on your input tape you can always refer to that and probably you can replace this with some constant so yes if you solve this what you will get is something like order n times m right but what you are saying so then you have to look at what the base case is so the base case is when you have 0 variables so s of 0 comma m will require some size m right so what you are saying then will require n plus m yeah yeah you are right but yeah it does not quite matter because we have sufficient space yeah so yeah so and yeah the hardness part also can be shown again not with much difficulty its basically again ah looking at the configuration graph and then looking at adjacent configurations and coming up with a formula that encodes the definition of an edge between adjacent configuration so you write a formula which is one if there is an edge between two pair of configurations and which is zero otherwise and you appropriately encode it into a ah thing so i won't go into that part uh so let us come back to our discussion of polynomial hierarchy and lets see how this thing fits in so ok so what was the definition that we saw last time so it is the union over all i greater than or equal to 1 of the classes sigma i p ok and what was the definition of sigma i p yeah so it is basically a generalization of the class np where instead of looking at just one the existence of just one certificate you look at alternative i mean you look at ah in an alternating manner whether there exist different certificates with the universal and the exit existential quantifier ok so let us just write that definition down once more so l is in sigma i p if there exist a machine m and a polynomial q such that for all strings x x belongs to l if and only if there exist u 1 such that for all u 2 so on till some quantifier q i ui the machine m with x comma u1 comma ui evaluates to 1 okay where all the ujs have length ah q of mod x and q i is an existential or universal quantifier depending on whether i is ordered even ok so this was the definition ok and one of you asked last time that why do we look at alternating quantifiers right i mean what if we have the same quantifier for two consecutive strings so can anyone answer that exactly so i mean if we have two quantify i mean if you have two strings with the same quantifier two consecutive strings then basically we can just treat both those strings as just a single certificate with that particular quantifier so let's say if i had a there exist u 1 and there exist u 2 i can think it off as the concatenation of u 1 and u 2 with the existential quantifier okay so what is the blow up the blow up is only in the length of the string okay but then i mean we have that freedom i mean then we can choose a polynomial q appropriately okay which is just twice the length of this polynomial ok i mean we do not care what that polynomial is as long as as it is a polynomial so a language is in this class if there is some machine and some polynomial ok so it is just that we will have a new q prime and a maybe a new machine ah which will deal with that and the same thing happens if i have a consecutive universal quantifiers as well and it is not only for two i mean if i have any sequence of quantifiers which are the same i can always club those strings together and put the quantifier preceding it okay so that is why always without loss of generality we can assume that the quantifiers alternate huh right so that changes the definition of the class so we will look at that okay so similar to ah sigma i p ok we define the class pi i p okay which is just a complement of sigma i p that is it contains the set of all languages l such that l complement is in sigma i p ok and now i think that answers your question so if we look at the class pi i p okay we can also i mean now since i have defined pi i p as the complement of sigma i p i can state this as a theorem that a language will belong to pi i p if there is some polynomial time turing machine m and a polynomial q such that for all x x will belong to the language if and only if for all u 1 there exist u 2 and basically again the quantifiers will not or i mean they'll alternate ah and they'll be i such quantifications and the machine accepts the string with all those certificates okay so the difference is that what is the initial quantifier that i am starting off with okay so yeah so therefore again we can define pi h also altern i mean the class ph also alternatively with respect to the classes pi ips so it is the union over all eyes of pi i p okay and again these are very easy to see also what can we say about ah the various sigma i's and the various pi i's so what can we say between let us say two sigma let us say you have a sigma ip and a sigma jp yeah okay so for j greater than i sigma i p is contained in sigma j p okay so this follows from the definition ok because if i have a higher j i can just ignore all the additional strings okay so that we do not know so we know that there is a containment but whether it contains any additional languages that is something again that we do not know so again that is a good question and people believe that all these containments are actually proper so people believe that within the polynomial hierarchy so basically these are referred to as levels of the polynomial hierarchy so they believe that all these levels are actually different from each other there exist problems in each of these levels which are not contained in smaller levels but that is something which is not known okay yes yes so yeah we will actually come to that so there are complete problems known for each of these levels and actually that is not something very easy to see i mean i can just state that if you just look at a generalization of sat again so what was sad sat was right i mean basically sat was ah i mean you have certain variables and you look at i mean does there exist values to those variables which makes it satisfiable but instead of that if you just generalize it ok so let me write it here so we can define the following language sigma i sat okay so sigma i sat is the it is a set of all formulas phi such that there exist some vector u1 such that for all u2 and so on some quantifier qi with a vector ui such that the formula phi with all these vectors u1 through ui is satisfiable so i can treat the variables in this formula as some set of disjoint vectors where there exists some assignment to the variables in u1 such that for all possible values that can be assigned to the variables in u2 and so on all the way up to ui this formula is satisfiable and this is complete for sigma i sat i am sorry for sigma ip okay i think this is actually an exercise in ah in your textbook to prove why this is complete so this is again not difficult to show but yeah so this is something which is kind of derived from the the definition of sigma ip i mean whether there exist other natural problems which exactly characterize these classes or not that is something interesting and i think up to the second level of the polynomial hierarchy there are complete problems which are known ok i mean there are other natural problems which are known to exactly characterize for example sigma 2 p so sigma 1 p is nothing but n p right for sigma 2 p i think they are unknown but for sigma 3 and 4 you can come up with artificial definitions but yeah i mean i don't know what exactly what you want ok so yeah so just coming back to this thing ah what about let's say the relation between a sigma i p and a pi i p what can we say about these two classes maybe for a different type so maybe let's say we if we have some j so pi j p is co sigma j p right it is content in this yeah so in other words what we can write is uh for any actually i plus 1 i mean if i look at just pi i plus 1 p so this contains sigma i p okay because again what we can do is we can just forget the first quantifier ok so we have some other still i quantifiers left which begin with the opposite quantification okay and in the same manner this is contained in sigma i plus two p so i am i am stating these theorems but you guys should go and just work this out and convince yourselves so they do follow from the definitions but it's good to actually work them out okay yeah so the reason why i stated why i digressed and i talked about this p space complete problem is that so now again we can see quite easily that for all i okay sigma i p is contained in p space yeah so maybe i shouldn't have erased that language and the reason for that is if you look at the complete problem for sigma ip that i just ah actually erased out so that is nothing but a special case of the tqbf language right so it is just a special case where we are only looking for some small set of variables okay and what we get as a corollary is that this entire class p h is also a subset of p space so there exists this entire plethora of classes and natural languages which sit between the class np and p space which makes a case as to why we study this hierarchy pi so ok so let us look at another theorem that if p is equal to np then the polynomial hierarchy also collapses to p okay this is what is referred to as the polynomial hierarchy collapses so again this is something that is not believed because ah the hypothesis of this statement is not belief but let us look at a proof of this so yeah very difficult but let's look at it so we will prove this by induction so what we will show is that for all i sigma i p is contained in p okay so that will immediately imply that the polynomial hierarchy is contained in p so for i equal to 1 this follows from our hypothesis if i is equal to 1 then sigma 1 p is by definition the class np which is equal to p by our hypothesis so therefore the claim holds true okay so suppose it is true for i minus 1 okay so how do we show it to be true for i so let l be a language which belongs to sigma ip so this means that there exists a polynomial time turing machine m and a polynomial q such that x belongs to l if and only if there exists a string u 1 such that for all u2 some quantifier qi ui m on x 1 x comma u 1 up to u y evaluates to 1. and all the ujs belong to ah have size q of x so now we can define a language l prime based on this language so so let us define l prime which is the set of all tuples of the form x comma u1 okay such that for all u 2 there exist a u 3 q y u i ah and m given x comma u one comma u y evaluates to one ok so i am just clubbing u one ah together with the given instance x so now what can we say what can we say about l prime minister it has i minus 1 quantifier and it begins with a for all so therefore l prime belongs to pi i minus 1 p okay and since we had assumed earlier that sigma i p belongs to p ah right right no no no here we have assumed that sigma i minus one is belongs to p so if sigma i minus 1 belongs to p since p is closed under complement pi i minus 1 also belongs to p right so this also belongs to p since it's yeah so that we still do not know but we what we can say is that since this ah is equal to p and p is so this we know is closed under complement well does not matter because p by definition is a subset of all these classes so we can write equal to also ok so if this belongs to p that implies that there exist some deterministic some polytime deterministic turing machine m prime such that l prime is equal to l of m prime so now let's go back to the language l prime so when do we say that language i mean an instance is l prime uh so by our definition for all strings x we know that x belongs to l if and only if there exist u 1 such that m prime given x comma u 1 is equal to 1. okay so that is what our definition of l prime was that there exist some u 1 which together with the string x and for all these certificates x gave us one so therefore so if you just check this so this is nothing but the definition of np so therefore l belongs to np which is equal to p so yeah so most of these theorems that you would see i mean they will have this similar kind of flavor because ah it is just basically cutting down on the number of steps in the polynomial hierarchy and then being able to prove something so actually we can generalize this theorem a little bit ok i just state it as a corollary so instead of assuming that t is equal to np even if you assume something ah much weaker that if okay so for all i if sigma i p is equal to pi i p then what do you think we can say about ph so if i just fix some i ok so it can be for any eye so basically do not confuse this for all i statement together with this what this means is that if you fix any i that is greater than or equal to 1 and if for that particular i sigma i p is equal to pi i p what do you think we can say about ph ah well not quite so ph won't quite all the way collapse down to p but it will collapse to sigma i of p okay so we have all these classes so let us let draw small picture so we have the class p over here okay and we have the class n p and the class co n p so p is of course a subset of these two classes okay ah yeah so this is nothing but sigma 1 p and this is pi 1 p so where does sigma 2 p sit so sigma 2 p again encompasses both these and it is something like this so this i have you can think of this as sigma two p and you have similarly pi two p ok and the hierarchy continues so each level of the hierarchy contains all the classes in its lower levels okay and each level of the hierarchy i mean you can think that the sigma and the pi versions are in some sense separate so if for any particular level i if the entire polynomial hierarchy above it i mean if for any particular level i these two classes coincide then basically what is happening is that the entire polynomial hierarchy that is sitting above it will collapse to that particular level ok yeah it does not imply that even the lower classes would collapse but at least we can say that the highest higher ones would collapse so yes huh which one this one no it's not for one particular it's for any eye right no so so that is why so yeah so maybe i can just rephrase the statement slightly differently ok so fix i ok now if sigma i p is equal to pi i p then it collapses to that okay so this i that i am fixing can be anything so that is what i meant earlier no but there exist again i mean i don't i mean depends how you interpret it but there exist would mean that for some particular i this is happening it should be fine as long as you understand what is happening so that is what is important but yeah ok so again this you can just try out as a proof the proof is nothing is just just its very similar along these lines where you have to prove it inductively just you have to start your induction from this particular i instead of from i is equal to one okay so i will stop here today [Music] [Music] [Music] you