Video 8-4: Boolean circuits

0:01 Before we define formally what pseudo random number generators are in this context, uh I said we have to pick a convenient model of computation and um maybe this is not the only one that can be made to work but it seems to make some of the proofs tick and uh so uh we're going to dive a bit into this. That's the model of boolean circuits.

0:31 The reason again here is just for random numbers generators. Uh that's the purpose to introduce it here as an alternative to Turing machines. Uh it does come up in complexity theory in many places as a a convenient alternative to look at things. Uh it actually popped up very briefly in the FPT chapter for for WP hardness. Uh the right notion was the weighted SAT problem on circuits. uh we didn't properly define things there because we only needed the uh the intuition. Uh but now let's do it a little more carefully so that we can at least define some of the notions. Uh what's a boolean circuit? Um I drew the picture back then. Let let me just make up some arbitrary example to make the definition clear. As in a boolean formula, you have some inputs. These could be just variables. And then you have different gates. You can have a notgate that um takes the value that you get in and outputs the negation.

1:34 Or you can have an AND gate. So maybe these two go in here. And then you can have an OR gate that takes the output of this one. But maybe I have an orgate that takes the output of this one. and takes variable x1 as well and repeat x3 in here. And then we do another another and ant. Okay, I'm probably making up a not so interesting function.

2:17 And then we'll have an output somehow marked that's the only sync. So formally it's just a a directed graph um an asyclic graph otherwise you can't properly define the function computed. It needs to have a s single sync I called it C. So let's call it C. It's called C because capital C is the circuit because this little C represents the the output. And then we have gates in this um for boolean circuits somewhat arbitrarily fixed to be and or or not. Um but that's just uh the way we will we will define them. Uh and and crucially we'll um restrict ourselves here to uh the gates having a fixed fan out um to and in to out. In general, you could build circuits where you allow many more inputs, but then you get different types of uh sizes for the circuit and that's going to be uh the next crucial bit. So, I hope intuitively is somewhat clear how these work. They're very close to how uh uh semiconductor circuits really are built. Uh at least the the one abstraction level up.

3:28 The value computed by such a circuit is just recursively uh computed. You put the variables in the variable uh vertices and then you evaluate in a kind of uh traversal through the graph. You can assign um each vertex a value. So let's maybe do that here. So here x1 that becomes zero after the negation. Then let's do this orgate. There's a one going in from here and a another thing that we haven't computed yet. So here's an and between zero and that's a zero. So there's a zero going in for this or gate but or is still one. X3 is zero and this is a zero still. So this or gate is zero. So the and gets one and zero output zero. So in the end the output here the computed value is zero or false.

4:33 And you can define this just over the graph. Uh the crucial thing about circuits is their size which is just the number of gadgets or the number of uh uh gates I should say number of vertices in the graph. whether or not you count the number of variables uh in this here I guess I'm uh I'm not fussy about so let's say it's just all the vertices in the circuit um that's that's just the definition um and we'll connect it to some other things later every circuit that you can write down will compute some boolean function if it has n variables and sources. Then it will compute a boolean function with an input from 01 to the n and it'll output a single bit and uh that's the function computed by the circuit and then we can define the first non-trivial thing uh the circuit complexity of a boolean function. If you give me an arbitrary boolean function, you can ask me what's the smallest circuit that computes this function.

5:47 And that turns out to be a a very hard question in general. Uh some boolean functions obviously allow a specific circuit and then maybe uh that's so small that you can prove that there's no smaller. uh but for many other functions we feel like um you cannot build a small circuit but we can also cannot pro we can also not prove it. We don't know whether it's possible to substantially shrink the circuit. Um here's a concrete example just to demonstrate some some concepts and also this this uh uh size uh this circuit complexity. It's a classical function in this area. The parody function just computes how many um bits well is there an odd number of of one bits in the input. So uh essentially it's taking just the x or of all the inputs and uh you can conveniently write this as just the sum modulo two is all the it's a very simple function but um it turns out it's not so convenient to write a boolean formula for this.

7:01 First of all xor is associative because it's the addition in this in this uh ring modulo too. So you can uh always split off the last x or say you can rewrite x or using the standard boolean uh basis of and or not. And so this uses uh five uh circuit gates. So you can by iterating this construction splitting of the last variable you can build a circuit that uses roughly five n gates and people have played this game to reduce the constant five a little bit. So 5n is not the best possible. You can be a little smarter but not sub not much just a a small constant factor better. Um by contrast if you look at boolean formulas it seems not so clear how to make a small formula. Um indeed the obvious way how we build it here with um a circuit if you replace the last xor by this uh equivalent expression you're you're using the one smaller formula twice in a circuit that's fine because you can just take the output from the previous part and use it twice. uh but for a boolean formula this is uh this is not going to work and so if you expand that you actually get an exponential blow up.

8:28 Now of course you can be smarter one way to um if if you have an nfold operation and it's associative of course you can break it up at any point. It doesn't have to be the last or the first. And so maybe it's much more natural to say I'm I'm taking parenthesis around the middle instead of splitting off one thing if I'm running into this kind of issue. And so you can use uh this recursion the number of bits is odd if the first half is even and the second half is odd or vice versa. That's exactly what this formula expresses. And then you can uh reduce the size of this boolean formula to n squ r roughly. And that seems to be it. I think it's not um I'm not sure if that's proven, but it seems not possible to do a a smaller formula over this over this uh basis. So you see already here that circuits are more powerful uh because they allow reusing uh calculations. they can substantially expand what you can express with formulas.

9:47 That was just an a little excursion to make that point. That's why in the previous chapter it made a difference whether we say satisfiability of a boolean circuit or satisfiability of a boolean formula. The input is smaller if you allow circuits and that makes the problem harder.

10:03 But you can also do uh use circuits as first class citizens in as a computational model. Um if you uh if you think about accepting a language over some alphabet, you fix some encoding of that language into binary, the binary representation is fed into the input variables of a boolean circuit and then the output of the circuit can be yes accept or no reject. Right? uh if you do that um you can get the the class P / poly which is the class of all polomialsized circuit solvable problems.

10:44 So it's all functions of all languages because they're boolean functions is equivalent that can be computed with polomial sized circuits where uh if the function is a general problem restricted to inputs of size n only needs a circuit of size n to the c. Um some obvious thing like a a touring machine can always simulate the circuit by just um inserting the variables and outputting uh the output. But uh there's a there's a slight catch. Um we can do this for a fixed input size.

11:46 But what this statement here really says is that for every n there is some circuit and it could be a different circuit for every n I'm just going to write f restricted to inputs of size 01 to the n and if if I'm fixing a specific input size then I can always take a touring machine that just uh takes the circuit as an input and simulates the evaluation. Um, interestingly you can do the other direction too. You can take any uh you can uh take any touring machine that runs in time t of n and on in on on size uh n inputs and you can turn it into a circuit that computes the same function and you get a slight blow up in the size. um you get squared the size of the time. Um there's there's two reasons why I'm listing this here. We're not going to prove it. It needs uh a certain normal form for Turing machines. That's not so relevant for us. Uh first of all, you can you can transform any circuit into any Turing machine into a circuit. H and what happens is that the time of the Turing machine turns into the size of the circuit.

13:30 Right? So uh you should keep this in mind that the size of a circuit is really the equivalent of the time taken by a Turing machine. And think of the simulation if you go the other way around. If you have a circuit and you want to evaluate it by a Turing machine, you have to go through every vertex and compute. If you do it in a smart order, you can do it in linear time. You have to do uh the calculation for every vertex in this directed graph and then you receive the output. So the time you spend for that is the size of the circuit and you can go the other way around which is a non-trivial uh proof but um I'll just state that here as a fact.

14:25 Now uh as I said before this this class of functions p/pole is a bit awkward because you're allowed to design a different circuit for every input size and that also means you can cheat in specific ways. Um in in particular this p/polley contains a few problems that you shouldn't be able to compute in a reasonable model of computation. It contains certain broken versions of the halting problem. Uh but really what's behind this is just that uh any unary um any uni unary language where uh so any language that's a subset of just having one to the n for all n meaning it has a single word of every length if it has one or it has at most one word of every length. Uh these are trivially um in poly poly because restricted to one n the language is trivial. You just check if the input is all ones. Uh but it turns out you can encode certain halting problems into such uh such a language. So it's it's a bit um of a strange model of computation for general purposes.

15:51 All right, the other bit is uh is not completely uh without bounds. Um probably NP is not uh subset of P/P poly which means these circuits cannot simulate non-determinism. That's not a proof but it's not a proof in the same way as uh we don't know whether NP is not a subset of P. It could be equal. So the then it's not so surprising but uh there's slightly different assumption behind this. Uh so I guess if NP was a subset of P poly it wouldn't directly imply that P is not equals NP. It would just make the polomial hierarchy collapse.

16:40 What uh what's known about these um complexities of functions is that uh it's a bit paradoxical. If you take a random boolean function generated by picking for every input a random zero on output, you're going to end up with functions that require exponential size circuits almost all the time.

17:03 And that follows just from a a simple counting argument. But at the same time, for any kind of interesting functions that we look at, specific functions, it seems incredibly hard to prove any meaningful circuit lower bounds.

17:18 And uh it it sounds first like um a contradiction, but the point is that the first statement really is about functions that wouldn't have been efficient to compute. The only way to compute them is to run an exponential size circuit. So these are not in in P and not even in NP most likely at least unless um yeah they're most likely not in NP. Uh I think that's even even provable.

17:54 Whereas these functions that we care about, they're they tend to be functions that are efficiently computable because they have them some specific structure. At least they want we want them to be in NP.

18:06 And if you think about this for a bit more, then you see that proving an exponential circuit lower bound for any function in NP would immediately imply that P is not equals NP. So that's going to be very hard to do. Um and on the other hand the explicit lower bounds that are known uh like for the parody function that's roughly the best we have uh linear in n as the circuit lower bounds is is the typical kind of result and that's a lot of uh slack between those two obviously.

18:48 Now for our pseudo random generators that we'll we'll come to in on the next slide, we'll need a slightly uh a slightly different notion of um computing a function. Um I should really have put this Monte Carlo circuits here in in quotes uh because it's is not exactly a that is it's rather an average case thing. So the um the hardness of a function or the uh definition before here um definition A10 circuit complexity of a function uh is just the smallest circuit that computes the function full stop. Now we're going to weaken that by saying what's the smallest circuit that computes the function at least on most of the possible inputs. And so uh you have to you can quantify what most means. That's this row. It's if you pick um the inputs uniformly at random then uh you want a row fraction of all these inputs to be computed correctly via some circuit C.

20:06 And then we say that this this row average case hardness of a function is just the size S of a circuit. So that all the circuits that are not larger than S can only get a row fraction can can get less of a row fraction correct. There's a bit many negations involved. Uh but the point is if you want to compute a function with higher and higher confidence for more and more inputs, you're going to need to represent it more precisely and that's going to need a larger circuit. So I guess it makes sense that this um average hardness goes up with uh a larger row.

20:53 Um and that's the that's the average hardness. So you you you don't need to compute the function for every input just for most of them. And then a slightly curious notion that just makes sure we don't have another parameter flying around is this uh average case hardness of a function and that's defined as as the maximum of these terms. So in a way you're using the same parameter for the size of the circuit. Um, and for the uh guarantee that you have for the uh confidence threshold, you always want to be correct at least half of the time, but then how much above the half of the time you let that go down with larger S. And so in a way again it makes sense that this this maximum exists because with larger S, you allow more circuits and you allow them to have more errors. And this kind of a putting the trade-off between these two on a single line.

21:57 This may may look really a bit arbitrary and in a way the definition I suppose is inspired from its uses later. But intuitively it's a way of of saying how complicated a function is in this average case sense. A function is complicated in this sense. So it has a large average case hardness if really you need a big circuit for most of its inputs.

22:27 And here's the key hypothesis that we'll we'll rely on. Thus is this is our equivalent of P is not equal NP. uh we'll hypothesize that there is a function we can actually slightly um weaken this part but a function that's reasonable to compute in general but whose uh average case hardness is still exponential.

22:59 Now let me um make sure I'm saying this in writing twice and verbally as well. This is not proven. It's a working hypothesis, same as P not equals NP. It's widely believed because we'll have some evidence for it in a second, but it is not proven. We don't know whether that's true. Okay, but that's uh where what we'll run from. Uh there's there's two bits that make it somewhat plausible that this could exist. uh number one is a a lengthy excursion of his own that I I didn't want to go into. uh but you can show if there's any function where the um where the worst case hardness is large so where you need a large circuit for all possible inputs then you can actually construct some other function um uh I shouldn't have put the same f here it's a different function say g where the average hardness is also high and that's um maybe somewhat surprising it's a clever construction ction, but that only helps us if there are functions that have high worst case complexity and these we don't know. But again, it looks like things like threes if you represent that problem as a language and encode it in circuits.

24:18 Um that probably needs exponential size circuits. That's roughly like the exponential time hypothesis. It's not formally equivalent in any sense I know of. uh but I feel in in spirit it's it's similar. It's it's roughly saying you need exponential time for threes and it turns out for circuits there's no reason to believe that you get a enormous speed up from doing it on circuits as opposed to on touring machines and there's other candidates for this part. So it seems relatively strongly supported this hypothesis. Uh not quite as strong as P not equals NP but somewhere in in that range. So maybe we can uh assume that for now and uh work from there.

25:16 And so that brings us to the the key definition for this part um which is what do we mean by pseudo random bits. That's coming back to the beginning. And the formal definition here is essentially using circuits instead of fast programs. we call some some uh fixed string of m bits s epsilon pseudo random um if every circuit up to size s will uh lead uh to the same result for most of the inputs. So if you p if you put into the circuit um a uniformly random chosen input and R then the output will be with probability epsilon only different which means only for an epsilon fraction of all possible inputs can you uh differ on can the circuit differ on that input from the the uh the circuit ah holy cow. Is there an equals one missing?

26:30 So if um if the circuit on R outputs one then uh it should output one for for the other random for the truly random inputs and the probability here is over over u right over the random inputs.

26:51 So whenever you use those inputs in a small enough circuit, you cannot distinguish them with probability more than epsilon from truly random bits. That's that's the thing. And again remember that small circuit means fast algorithms. So it's the equivalent of the uh it's an instantation instantiation of the uh intuitive definition, but it uses circuits of a specific size.

27:22 This is for um a fixed um bit vector R which is uh in general not what we want. We want something that can generate bits and uh of arbitrary size. So the pseudo random generator in in its full beauty is a a function G that gets um seeds of a certain size L and outputs a much longer bit string S of uh G of of the input of size S of L and uh we want that it is computable in in exponential time sounds maybe weird, but that's good enough for what we want. Um, its output is always uh s of the input size. So, it's increasing the input by exactly the same amount each time. And its output is pseudo random in the above sense. And uh arbitrarily we pick 10% error chance for the pseudo randomness from above the epsilon. And the size of the circuit is cubed the size of the blow up that we have. So we make out of L we make S of L pseudo random bits and we need those to be pseudo random up to a circuit size of S of L cubed.

28:46 A lot of seemingly arbitrary uh constants and some of them the 10 and the three are somewhat arbitrary. You could there's different choices. these just turn out to be convenient for the proofs.

29:04 Okay, so so far um not much has happened to the intuitive definition except that we call something pseudo random uh specifically if there's no small circuit that distinguishes it from actual random. And a pseudo random generator has these parameters that make it a bit unwieldy. But uh the whole the whole beauty is to bring everything into one parameter and that's this blow up. uh how many more random bits can I generate out of L seed bits and then all all of the rest is uh expressed in terms of this function s of