Video 2-2: Models of Computation

0:02 In the next section, we'll look at models of computation, which we really need to make statements of the kind that we want. Namely, if an if we're trying to prove that a certain algorithmic problem is not in P. I know we won't be able to definitively prove that, but let's suppose we want that. At least we need a way to make a statement about all algorithms that I could write down have a certain property. Maybe all algorithms that solve this problem don't have the property of running in polynomial time. And for that I need a way to say, what is this thing all algorithms, right? And that's uh you could say it's all valid strings that compile if you feed them to Python or something like this compiles that run when you feed them to Python's eval or so. This is rather inconvenient to do proofs of about. So, instead we'll look at some more abstract models of computation. That's what we'll uh what we'll look at here.

1:00 And a model of computation, for example, has to say what kind of operations you're allowed to do and how much time or other resources they cost. And so, for this question, even the innocent addition of two numbers it may not be 100% obvious how much they should cost.

1:17 And um it's lovely that even in a small group people disagree on this. Now, the truth is you're kind of all right. Maybe logarithmic in D I find hard, but it's the number of digits, not the uh value of the number. Then um logarithmic would also be correct. Uh in a way, there's no single answer that is correct. It depends on the model and it depends on the numbers. So, here all I want to do is draw your attention to this to this fact. And in classical literature on on theoretical computer science, there's usually um even two fixed names for these two extremes. If you can uh, add up numbers in constant time, then that's called the the, uniform cost model, which just means that any arithmetic operation on numbers takes constant time, and that's what you count. Now, this is not really what we'll usually look at, because maybe you can imagine that that you can cheat a bit in this model. You can encode a whole lot of things into one enormous number, and then, in one time time step, add it up with another number, or do even bitwise tricks, and then it gets extremely cheaty.

2:40 So, this model seems appealing, um, at first sight, but for complexity theory, it's not very suitable. The other option, confusingly, is called the logarithmic cost model, because it's logarithmic in the value of the number. But, if you write the number down as bits in a sensible encoding, for example, as binary number, then the number of bits would be logarithmic in the value, but D is already this length of the number. And then, adding up two numbers, as you've done it in primary school, takes exactly linear time in the digits. I you start at the right, add the two digits, maybe have a carry, then add the two digits and the carry, and so on. And in each step, you produce the next output digit.

3:28 Isn't that a problem, though, that like I have two answers marked correct that are contradicting each other? How can the same operation take, um, both constant time and time proportional to D? One option is to say, "Ah, that's just two different ways to look at the world, and you have to decide." That's a bit unsatisfying for the practical side of computing, because we feel, depending on the application, that we're both in one of these two worlds at the same time. Uh For example, if you have um ints, not integers, but int as the built-in type in Java or C or any of these languages, you can indeed add those in constant time. Whereas, if you have big integer in Java or some other language that has arbitrary precision numbers, then you are in this world where addition takes time proportional to the length of the number. So, it depends on the size of the number in the end at the end of the of the day.

4:33 Okay. I think this very We discussed already the the need for a mathematical model of computation arises from this wish to prove something about all algorithms. And so, we need to be a little bit precise what we mean with uh the cost of a computation.

4:50 And in algorithms in general, the model of choice is this one, the random access machine model or the word RAM model, to be more precise. Where you can think of this is a model that comes close to most processors. So, you have uh you have memory, that's your main memory, that you can access by index or by address. And you have a small fixed number of registers which are close to your CPU that you can calculate with. Um Now, the the bit rate deviates from kind of any physical computer is that the size of these numbers in the memory or in the registers is not fixed, but is a parameter of the model. You're working with W-bit integers. These days, W is usually 64. In the past, it's been growing a bit from maybe 8 to 16 to 32. If you in include SIMD instructions, you could argue it's already at 256. Uh depending on on what exactly you count, here it's a formal parameter of the model. So, the machine has um a parameter that you specify.

6:02 And now the uh somewhat crazy thing is we assume that this parameter is tied to the input size. So, if you make your problem bigger, you need to buy a bigger machine with wider words. That's the assumption. And for for this model, let's just leave it with the only sensible assumption the only sensible model that gives you realistic and sensible extensions from what we currently have to the case that algorithmics becomes um bigger and bigger or input inputs become bigger and bigger is such that these parameters are coupled together. But, the word size grows roughly logarithmic in the input size. And the operations on this machine are then again closer to what real hardware would do. There's a way to read and write memory into registers. And there's the usual operations on registers. >> [snorts] >> Then you can define the time as just the number of steps that this machine takes. And here for the practically inclined, I'm I'm ignoring that access to memory in any practical machine is way slower than say adding two numbers. In this model, this is all the same unit cost.

7:16 Now, this model is fine. You can write down algorithms. Uh the experienced assembly programmers immediately spot that this is bubble sort or maybe not. Um there's even a famous algorithms book. I suppose people know Don Knuth or know that he exists. I don't know if you've met him in person, but uh he wrote these um influential books on algorithms that many people buy and not many people read. And one reason why many people don't read them is that it describes the algorithms in essentially assembly code or word RAM programs, if you wish. It's a very low-level way of specifying things. Which is my um my pointer to the fact that this model is closest, if you want realistic asymptotic statements about performance of algorithms. It is a bit inconvenient to work with. Now, for um for a module that is concerned with studying algorithms in more detail and making precisely the fastest method for some tractable problem for some efficient problems, say sorting algorithms or so, you would rather want to stay in this model, but program it on a higher level.

8:33 For complexity theory, we'll go the other direction. We'll make the model way, way more restrictive, so that the algorithms are even less convenient to program. So, there will be an even further gap between the actual model and the way we think about it and write programs. Essentially, it's not even pseudo code. What we'll What we'll describe is usually just the idea of how to make a machine that would work like this. You'll see on a few examples what I mean by that. It's usually fine because we don't care about the exact running time. We're very lenient in the context of complexity theory with if something takes a polynomial factor longer, that's fine. Yeah, sweep that under the rug. Okay, so it's a departure from the usual types of of algorithms that um we may work on in some undergrad algorithms class. It's really more at the very coarse scale. Very very slow versus not super slow.