Lecture 18 : Part B

[Music] [Music] so randomization has appeared here and now we will use it to define a new kind of touring machines with a new resource which we call randomized or probalistic touring machines okay so probalistic so you have seen deterministic touring machines uh non- deterministic touring machines and now this is a third type probabilistic touring machine where the resources like the previous resources were time space non-deterministic bits and uh we also use the for all quantifier to get the poly hierarchy um now the resource will be random bits okay how many coin tosses so let's define so call M A problemistic touring machine if it has two transition function functions Delta 0 Delta 1 this part you have seen already in ndtm ndtm also had two transition functions the same thing except now um during machine may flip a coin and decide which to choose in every step and uh in each trans ition step M randomly follows Delta I with probability uniform probability right so there are two choices in every step and with uh probability half during machine picks one note that this has to be done in every step it's not that Delta 0 or Delta 1 is fixed in the very beginning right so in every step one of these could be picked think of Delta 0 as head and Delta 1 as tail so um we say that M decides a problem L if for every input string X is in L if and only if so what happens with the yes strings yes strings are uh characterized by am accepting it with a good probability so probability that MX is one this has to be high okay and this probability is over the random bits basically the number of steps if it is uh t then there were t uh coin toses or random bits um pigged and so over that the probability of M accepting X should be 23 um and so it also means that if x is a no string then this probability should be 1/3 or less so thus uh X is not in l if and only if this probability of acceptance is less than equal to 1/3 okay so the um the error probability is essentially 1/3 so success probability is 2/3 right so for a yes string acceptance uh or non acceptance should be with probability 1/3 or less and with a no string the acceptance should be with probability 1/3 or less so let me maybe write that here it's MX equal to 1 we are talking about okay and uh what is the number of steps in terms of input size right that also we've uh that is the resource of time time right so we also want uh that to be minimized and uh the notion of efficiency Remains the Same that number of steps should be polinomial in the input size so so we can now talk about efficient PT right which probabilistic Turing machines are efficient and which are inefficient so that notion is by now it's uh easy to guess so for a function T measuring the time complexity PTM m decides l in TN time if M hals on every X in at most T size of X steps regardless of the uh random choices and decides whether X is in L or not right so again uh there is an important Point here in the time complexity we are saying we are defining time complexity as T of n if no matter what choices were made in the steps the random choices right the number of steps is always is upper bounded by T of size of X then the machine hals the PTM hals and gives an answer okay and that answer should be correct with probability 2/3 wrong with probability 1/3 so with that understanding we are now into randomized polinomial time algorithms uh well current yeah in this definition t is anything so let's just Define a complexity class first then we'll specialize to efficiency so BP time T of n is defined to be problems L such that a PTM [Music] m decides l in bigo of so this is like d time but uh now it's on PTM and with that notion of time complexity you collect all the problems which can be solved by a PTM in bigo of T time right so this is ASM totically T order T time and just like we moved from D time to the complexity class P we can now move to BPP so BPP is the union over BP time polinomial in N right so n to the C for a constant C but it can be any constant so this BPP stands for uh bounded error probabalistic polinomial time okay so it's the BP operator over p and BP operator means uh it stands for bound error probabalistic so it is probabilistic but uh what is the error probability that is also being specified it has to be bounded which means constant okay so we have fixed constant to be 1/3 and success as 2/3 so this uh bounded error is for example 1/3 the name um also has PP in it right so which is problemistic poly polytime so what what is the difference between these two so PP which is problemistic poly time um there the um success probability was just half right so error could be as big as half has the error as large as half right so the key thing here is that this 1/3 is less than half so it's away from half okay so if you take the error to be away from half then it's BPP if it is very close to half or half then you get PP and that actually changes everything so we will see later on that uh BPP is um it actually models practical problems which can be solved practically and PP as you have seen models very difficult problems so BPP models practical algorithms while PP is interactively hard right so there is a big difference between uh BPP and PP while if you look at the error that is just half versus 1/3 right so this thing might be a bit confusing um but uh you can think of half error as being too big okay half error doesn't give you uh any information because remember it's half both sides and that is the problem if it was one-sided it would have been okay but since it's both sides it doesn't give you any information okay so now let us uh go through easy properties that immediately follow so p is uh clearly in BPP why because uh in BPP in the PTM you may say that uh there is only one transition function right so then every step with probability one it is being picked so that's like a turing machine deterministic turing machine BPP is in PP why because uh well 1/3 error probability is smaller than half error probability so the pp definition also goes through PP you have already seen is in PS space which is in X right but as I remarked before uh p and BPP are kind of at the lower end of the spectrum they are efficient algorithms and PP and above is the other end of the spectrum the inability in computation so alternatively so we can also give a definition without using PTM how so alternatively L is in BPP if there exists a deterministic poly time during machine M and constant C such that for all input uh X is a yes string if and only if this deterministic PO time during machine actually takes the input X and also a random also a string R you can think of it as a certificate a random certificate which is not too big okay so and the probability over these uh random certificates is 2/3 for the yes strings and 1/3 for the No Strings so this you can think of as a random certificate for the yes strings X okay so this is the this there exist for all the quantif the quantifier based definition so this definition is above a deterministic polytime touring machine okay you can see that PTM and this definition are actually equivalent it's a same thing whether you say that the turing machine is making a choice in every step or you say that the choices are provided in advance they are random choices and most of the choices work right this 2/3 around 67% of the choices work that is what we are seeing and uh again this is very different from NP so let me ask that as a question or as an exercise so if you're calling it a random certificate then by this point of view what difference do you see from the definition of NP right in NP also there you need a certificate R here also you need Certificate R so how does it compare with NP just think about that and this will also tie with this PP you will see how uh BPP NP and PP compare so uh BPP is closer to our notion of randomized polytime algorithm algorithm M solving a problem L okay so whenever we'll say efficient randomized algorithm or randomized polinomial time algorithm we'll mean this that the problem is in BPP and this is because we consider uh coin is an easy resource because we can simulate coin tosses right so since we can simulate uh a coin toss in practice we tend to think that asking for a coin toss is not a big problem okay so as long as you have a randomized PO time algorithm it can be implemented in practice so in your C program you just do a coin toss although U how fair or unbiased that coin toss will be that's a question uh you have to um resolve and then implement but certainly by looking at it you don't think that it's a difficult problem in practice Coos should be possible to simulate it so let me leave that as a question and now uh with all this uh Theory all these definition that we have given and the alternate interpretation that we have given um let us see some examples okay do these ptms actually help and they do greatly actually so examples of famous ptms okay so probalistic touring machines which were uh discovered first which were which were discovered before the deterministic touring machines so first example is primality so the question of primality is the most basic one in math so given a number in binary of course so n is given to you via login bits check whether if it is prime if it is prime say say yes if it is composite say no so um the first practical algorithm and in fact um randomized poal time algorithm was given by solo stzen randomized poly time [Music] algorithm and in fact it was the first uh efficient PTM itself it was the first formal um um first efficient formalized okay so before that these algorithms were thought of uh juristically but to actually uh give this algorithm and then analyze the error probability and see that it's actually a practical algorithm that is where Sol stzen actually um introduced this important concept via this famous example so primality example is famous for both the reasons that it's a first practical algorithm with analysis and also it's a efficient PTM first great example so what is this algorithm so it is quite simple um at least I mean it has just one step uh yeah but um I will not give the details of it so let me just give the algorithm in one step so what you do is you pick a random pick a random number a co- Prime to n okay so pick a number a from let's say uh 1 to n minus one if it shares a factor with n then you have already uh factored n so primality is done so assume that it is co- Prime to n and with this you check the following so output yes if e to n -1 by 2 is congruent to a number which can be computed easily uh this is called the yakobi symbol a by n just check this mod n so this is the yakobi symbol computed like uh gcd algorithm okay so this is some kind of gcd computation think of gcd computation for E comma n so that kind of computation do that so you will get a by n uh to be a sign okay plus minus one so this is actually a sign + minus one and just check whether it is the same as a to nus 1 by 2 if it is then you output that n is prime otherwise you output that n is composite okay that's uh that's an algorithm that is using uh random bits in terms of of a a requires around login random bits to describe right and this I leave as an exercise so you can see that it's a simple algorithm of you can if you know some number Theory you can also analyze the time complexity um the the error probability it'll come out to be um one sided error okay so when n is prime then this algorithm will pass through no errors if n is composite then there may be an error prove one-sided error of less than half and uh time complexity around quadratic okay but it's uh so remember that probability error probability can be close to half but it's actually one-sided error it's not both sided like in BPP definition so this is unlike BPP definition here it's the other is only one-sided so one-sided actually even half is good and uh yeah so this algorithm is better than uh BPP it means that uh primality is in BPP actually this also you have to show because it's why is the probability 1/3 both sides so actually with oneid error of half you can still show that um the error can be further reduced okay this is by boosting the success probability okay so just show these things if you are interested otherwise take this as a as an algorithm which is uh which is one of the most famous examples of ptms [Music] [Music] [Music]