--- Video Title: Complexity Classes: SIZE Description: Theory of Computation https://uvatoc.github.io/week5 10.2: Introducing Complexity Nathan Brunelle and David Evans University of Virginia --- So let's look at how it is that we're going to categorize functions by circuit size. So first of all, we know that we can actually provide an upper bound on what kind of the largest category might be. What the category is that's going to have all of the functions in it. We proved that no functions at all that map n input bits to m output bits require more than some constant times m times 2 to the n gates. We said that we could sort of exhaustively have variables for every possible input and then we could just do one big lookup on all of those variables in order to compute any function at all that we wanted. And that procedure, that took us approximately m times 2 to the n gates in order to do that. So that procedure basically proved to us that if I consider the category of functions that require no more than m times 2 to the n gates, that's going to include all functions mapping n input bits to m output bits. So now we already know, here is some big bucket that every single function of a certain number of inputs and outputs fits into, no matter what. Some functions might also fit into smaller buckets, but certainly every function fits into that bigger bucket. We also do know that some functions require many fewer gates. For instance, when we looked at if, if required like 4 gates to do or something like that. Way less than this m times 2 to the n bits. What we can see, certainly from this example, is that some functions are going to be more complicated than others, so we're going to start categorizing functions by the resources required to implement them. And the way that we're going to categorize them is we're going to be bucketing them based on the size, based on the number of gates, in the most efficient way of implementing that function. So if we consider all of the ways to implement the function, we look at the one that required the fewest gates, And that tells us which bucket our function is going to fit into. And the way we're going to refer to that bucket is size S. S is going to be some natural number. So size of S takes as input a natural number and maps to a set of functions, which says it's going to be all of the functions that can be implemented by a circuit using at most S NAND gates. So we could say that something we proved last week was that size of maybe 1,000 times M times 2 to the N is going to contain all functions mapping N input bits to M output bits. So this bucket here, size 1,000 times M times 2 to the N, is going to contain all of those functions. Just to show where some of the notation from the book fits in with this, the book will also provide some subscripts to size. If two subscripts are provided on that size, then it means it's restricting the number of inputs and outputs. Size without any subscripts just says all functions, all finite functions at all, that have that many gates, or at most that many gates, that require at most that many gates. When we add subscripts, we're saying functions that have a certain number of inputs and outputs. So if there's two of them, then that says that we're going to have n inputs and m outputs in all of the functions we're talking about. So all of the functions in those sets have the same number of inputs and outputs. If only one subscript was provided, then that's understood that the number of outputs was going to be one. So it says that many inputs and one output. So for instance, to talk about if, if was a function that mapped three inputs to one output. So if would belong to, let's say, size sub-3 of 10, or something like that. So if belongs to size sub-3 of 10, because it is a function that has three input bits and one output bit, and can be implemented in fewer than 10 NAND gates. Yeah. The 1,000... so we've proved that there was some constant. We didn't actually keep track of precisely what that constant was, but it was certainly going to be smaller than 1,000. So I just picked 1,000 as something that I knew was going to be big enough to include all of the functions. So one side effect that we get from these complexity classes, since our complexity classes sort of say, I want all of the functions that require no more than this many gates, we sort of get this nesting of complexity classes. If the number of gates I'm allowed increases, then I could only gain more functions in that set. So when I look at the set of all of the functions I can implement in 30 or fewer gates, that's certainly going to be a subset of the functions that I can implement in 499 or fewer gates. If we increase the number of gates we're allowed to use, we're certainly not going to lose functions. It's sort of the maximum number of gates allowed rather than the exact number of gates used. Now some of these might not be proper subsets. It could be that any function that I can do in 500 gates, I could also do in 499 gates. So certainly some functions are more complicated than others, but it might be that there's weird gaps in this, where there's no function that strictly requires exactly 500 gates, for instance. That just because of some unluckiness there, there's a few functions that require exactly 499 gates, and then there's a few functions that require 501 gates, but it turns out there's none that required exactly 500. If x is less than or equal to y, so if x is less than or equal to y down here, Then that means size of S is certainly a subset of size of X is certainly a subset of size Y. But this might not be a proper subset.