Lecture 02

So, now, whenever we define a circuit, it is with respect to a basis that is it is with respect to a set of functions which we allow to be the gate for that circuit. So, now, what are some of the standard basis that we use? So, firstly, we have examples of some standard basis. So, basis is the plural for basis. So, what are examples of some of the standard basis? So, we have the De Morgan's basis which is represented also as omega, it consists of the gate AND, OR and NOT, ok. We have the basis B2 which is essentially all Boolean functions on 2 variables and how many Boolean functions do we have on 2 variables? So, there are a total of 16 different functions. So, the size of B2 is 16. So, any gate can be any one of those 16 different functions. Another very commonly used basis is the basis which has have a name does not have a name. So, we have the NOT gate and then we have unbounded OR and unbounded AND. So, basically we have OR gates that can take arbitrary number of inputs and AND gate that can take arbitrary number of inputs. The way they are defined is exactly the same that is an OR gate with an arbitrary number of input is 1, if at least one of its input if at least one of its input is 1 and an AND gate with an arbitrary number of input is 1, if all of its inputs are 1. So, these are some of the basis, but there are other interesting basis also that that one can study. So, here is a couple of very simple results. So, the first one is of course a fact. So, there are a total of 2 to the power 2 to the power n function over n inputs. So, suppose if I consider a Boolean function going from 0 1 to the power n to 0 1, how many such functions are possible? How many different functions can I have that go that take an input string and produces a single bit as an answer? So, first of all note that the total number of inputs that are possible is 2 to the power n. If I have n input variables, each variable can take 2 different values as input. So, there are a total of 2 to the power input 2 to the power n input. Now, each input can have 2 output. So, therefore, each input either that input can be mapped to a 0 or that input can be mapped to a 1 ok. So, therefore, there are a total of 2 to the power 2 to the power n different functions over n variables as input. Now, when we have a circuit over n variables ok. So, now, we can actually compare ok. So, we can compare that ok on one side I have this many functions and on the other side how many circuits do I have that that can actually compute those functions ok and then we can actually compare that I mean it allows us to give bound on the size of circuit ok. So, my size I mean my circuit should have size at least so much. So, that it is able to compute each and every one of those 2 to the power 2 to the power n functions. So, we next is we define the star size A circuit as the number of gates not including the NOT gate ok. So, if I am if I count only the number of non NOT gates in a circuit that is what is called the star size of that circuit ok. So, and often it is interesting to look at the star size because one can often use standard techniques and bring down all the NOT gates to the input level. So, what are what one is left with is only the non NOT gates ok. So, the star size is often a interesting parameter to look at. So, here is the first result that we will see every Boolean formula has a circuit star size at most n into 2 to the power n. So, any Boolean formula. So, we have a sorry every Boolean not formula every Boolean function. So, we take any of those 2 to the power 2 to the power n many Boolean functions over n bit input. So, every Boolean function has a circuit of star size at most n into 2 to the power n ok. So, again to be more specific every Boolean function on n variables has a circuit of star size distance. So, how do we prove this? So, the proof is actually quite simple. So, we take the Boolean function and we look at the truth table of the Boolean function. So, consider the truth table of the Boolean function. How many rows will there be in the truth table? So, it will have 2 to the power n rows and in each row basically the number of columns that you would have is n columns corresponding to each variable. So, each row corresponds to each setting of the variable and each column corresponds to a different variable. Now, the value of the function can be thought of as taking an OR of all the rows and inside a row it is basically taking an AND of all the what are known as literals ok. So, whatever. So, if a variable is set to 1 in a particular row you take that variable in its positive form and if a variable is set to 0 in a particular row of the truth table you take the negation of the negation of that variable not of that variable ok. So, therefore, every row has we consider what is known as a sum of product representation. So, let me write this sum of product representation of this function. Now, in this representation every row of the function is represented by n minus 1 AND gates and there are 2 to the power n times n minus 1 many AND gates and then the way we combine all these products or all these AND are using OR gate. So, we have a total of there are 2 to the power n OR gate. In fact, to be more specific there are actually 2 to the power n minus 1 many OR gate, but that is 2 to the power OR gate. So, therefore, the total number of gates is equal to 2 to the power n into n minus 1 plus 2 to the power n which is equal to n times 2 to the power n and we are of course, not counting the NOT gate. So, this is the star size ok. So, any Boolean function on n variable can be represented by a circuit having star size at most n into 2 to the power n. So, this gives us an upper bound ok. So, basically an upper bound on the circuit size, but note that this upper bound is actually quite non trivial I mean quite trivial to obtain ok and this is a very large upper bound ok. Now, what if I ask questions such as that if I let us say bound the size to be polynomial what kind of Boolean functions are computable by circuit that have polynomial size or what kind of functions cannot be computed by circuits that have polynomial size ok. So, these questions become much more interesting. So, as we go along this course we will look at more and more such type of questions and we will also look at various types of circuits. So, not just any arbitrary circuit, but circuits that have depths circuit whose depth is bounded by something circuit which allows a certain type of gates and ok. So, I will stop here today. Thank you.