Video 2-2: Models of computation: word-RAM

0:04 So we've seen intuitively what we want to do with NP completeness and now we should do the work of defining in detail what what we mean by all these terms that uh I used informally on the previous slides and uh let's start with this um you can think about it I'll set it up uh just as a Okay, I'll leave the slide with the the answers. We'll see the results in a second.

2:42 Should be a few more people in the room than have thinking? Let's see the results. And uh I've allowed various things as correct answers because the point of the question is that uh it's not a very well- definfined question.

3:31 Um, you could either say it takes constant time because adding two uh integers say what's what's what's people's famous mo most uh uh wellsup supported programming language um Python. Yeah, Python is a really bad example because Python has these built-in smart integers that uh uh grow in Yeah. So C and Java, anything that's a bit closer to the silicon um is um makes this point clearer. If you have an int in C or Java, a machine word in the computer, you can add those up in constant time independent on how big the numbers actually are, right? It is true. And with 64 bits or even even bigger long longs, uh it's it's it's big numbers in a way. Um on the other hand what I mentioned about Python that if you make the numbers bigger and bigger they will eventually overflow a single word and Python is smart enough or uh is programmed to be like that that it then automatically swaps out the representation of this integer by effectively a string of the digits. And if you do that then adding up to numbers that are represented as strings of digits you have to have at least read the numbers. So it's going to be proportional to the number of digits no matter what. Even if you don't do anything smart and uh addition is actually not smart. So it doesn't need to do more more work than that. So fine, what does that mean now?

5:04 Right? Uh shouldn't there be a well- definfined answer? Um that's the point of this question to get you thinking about this. Uh in this case there is a well- definfined answer. That's the word RAM. We'll we'll come to that. Uh but whenever you talk about computation and whenever we talk about computation in the context of uh algorithm theory, we're thinking of asmtoics. We're making things grow bigger and bigger because interesting comparisons are usually only possible or the limit of input size is going to infinity. But if you do that, you uh always have to think about these weird questions inevitably.

5:46 Okay. Um to cut the story short there, let's let's have a look at the solution for this specific case. Um more more broadly in this module, we're we'll talk about complexity classes which are sets of problems that have algorithms of a certain kind or that allow algorithms with a certain efficiency. We had P and NP. P was the class of all problems that have polomial time algorithms in the simplified version. Now uh if we if we can't even um decide on what addition should take as time, how would that make for a sensible definition? How can I classify problems by having some algorithm without saying what algorithms are allowed and what costs they have? And so it's true in general there is no such universal thing. You have to always say what is the model of computation and what costs do you uh assign an algorithm um otherwise this question makes no sense. Uh but um and so we have to fix a specific machine model. It turns out that the question of P and NP is very robust against many of these changes and will make sense irrespective of many of the specific definitions. Uh but you still need to pick some of the definitions to get started and then you can prove that other models are not much different. Um I think it would be a misunderstanding to say oh because P and NP are so robust which is the outcome of a deliberation with many concrete definitions. It would be a mistake to say oh then it doesn't matter to define it properly because then some of the other bits where uh it does depend on details get very uh very vague and um and unclear. So what's a machine model? It defi it defines what is an algorithm. So what are programs? What can I uh write down as computational recipe? Uh how they are described? Some sort of programming language is usually associated with this. Uh and crucially what are the costs of an execution?

8:04 That's also part of the machine of the machine model. Uh and this is what I took from efficient algorithms. It should be detailed and powerful enough to reflect what actual machines do while at the same time unify the specific iteration this year um and hopefully be also simple to analyze. That's often hard to uh achieve all three of them at the same time. Uh but for um for for algorithm theory, there is a a standard model for complexity analysis that gets a a good compromise between those three goals and that's the the word RAM or the the random access machine for short. I'll describe the model briefly before we then actually pivot away from it, but I think it's worth having seen this because this is the solution to how to properly define this cost of addition. Okay, it's also fairly close to actual hardware still um unlike the Turing machine that we'll look at afterwards. So, a random access machine um has an unlimited memory. You you should think of this as being as big as you need it and when you need it bigger, you just add another uh another piece of memory to your computer. You grow the computer as the need for uh it to grow grows. So it's unbounded in principle.

9:35 Any specific computer that you can build will of course be finite. But we're studying the limit of making this bigger and bigger. Okay, one really big memory with cells of numbers. Um, a fixed number of registers, say a 100. Number doesn't matter too much, but um, it doesn't grow. And then each of these memory cells and registers stores an integer with W bits. And crucially, this this parameter W also grows with the input size. That's a key assumption of the model and that's what makes it sensible. Even though it feels strange to have a machine grow with its input, this is historically what happened to computers. So it's not so absurd after all. So if if you have W bits, you can represent numbers in this range. Let's stick with positive integers. You can simulate all else uh based on that. Um W is called the word size. That's what W stands for. A word in a computer is just the the piece of uh bits that it can work with in constant time or in one cycle. And um the typical assumption is that this word size grows logarithmically with the input size.

10:55 This makes sense from different reason from different perspectives. It means that you can store a pointer to a place in memory in one word or in a constant number of words. uh it means that um it also reflects a bit how how historically these word sizes have grown. That's what the machine looks like. And then we need to define what programs can be. And these are essentially um a low-level assembly language. So there's instructions to read something from memory and write it into a register and write it back. Uh there's operations to compute only on registers. You can do the usual arithmetic operations and you can do uh logical operations and then there's conditional jumps and that's pretty much it. That's close to a a risk instruction set uh that some computers have. Uh Intel CPUs are a bit of a mess, but um ARM what's in your phones is is not too far away from uh an instruction set like this.

12:00 I'm defining the model in this detail because now we can answer this question of what should an addition cost. Well, if the numbers are small enough to fit in one word or a constant number of words, it does take constant time to add them up. Whereas, if the numbers get bigger, you have to divide the the size of the number by W. That's the answer. And the question is, are the numbers part of your input size or not? That's that's for you to decide when you define the problem. The running time of such a a program is just the number of instructions that it executes roughly the number of cycles if you want and the space cost is the total number of memory cells that were ever ever touched. Okay, I think the definition may maybe is a depending on how much background in computer architecture you have, maybe it's a natural definition. Maybe it's a bit awkward. That's that's the standard definition that seems to make most sense for studying efficient algorithms. And I guess um we'll leave it with some some small concrete example what a program here can look like.

13:17 And the point here is not so much to read this in detail. This is a an implementation of of bubble sword from Don Canu's books which uh I quoted it earlier as one of those books that many people have in their shelves without ever reading. And um I guess one reason is that he writes his algorithms in um in assembly language that's not so dissimilar to this. I basically could translate his code on his hypothetical machine one to one to our madeup uh RAM machine and uh I didn't have to invent more detail. So uh he studies algorithms really at this low level of of detail. We don't normally do that and we won't do that in this module. uh what we actually do in this module will will come to uh tomorrow. Um the word RAM is great because it reflects at least for the CPU cost lots of actual uh architectures. Um luckily for this module for the course distinction that we are after polomial time versus probably not polomial uh a lot of the the details in the word ram model are not so important and we can get away with a at least theoretically more clean model of computation.