English subtitles

← 08-05 Snapshots

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. What this means is not for any given number of variables,
  2. we can write a Boolean formula
  3. that can be satisfied
  4. if and only if exactly what one of these variables is set to true,
  5. and we figure out that we can do this for any number of variables that we want.
  6. So now let's go back to snapshots
  7. and see what the Boolean formula
  8. that I just showed you has to do with these snapshots.
  9. Each snapshot, as we've said, basically consists of
  10. 3 components, so we have the read only number here,
  11. which is basically the input.
  12. We have program, and we have the read-write memory
  13. for immediate results and output.
  14. So now let's think back a moment of how we defined the RAM.
  15. When we defined the RAM in the last unit,
  16. what we said was the following.
  17. We said that whenever we're talking about memory,
  18. so this part here or this part here,
  19. then every single cell in the memory can not hold
  20. arbitrarily large variables,
  21. which means, for example, that
  22. this cell here could either be 0;
  23. it could be 1, it could be 2, and so on,
  24. but there's a certain limit of how large those values here can be,
  25. just as with your novel computer programs, too.
  26. They can carry very, very large numbers
  27. but there's a limit
  28. and that limit is some constant,
  29. so I'll just write c here, so if you have an 8-bit computer,
  30. that constant will be smaller, of course, than if you have a 16-bit computer
  31. and so on, but in any case,
  32. it will be some constant determined by the machine,
  33. and the same thing is going to be true all along the memory.
  34. So for each single memory cell
  35. that you have here,
  36. you have a constant number of possibilities
  37. for the values that this memory cell can take,
  38. so the size here is constant,
  39. and here, it's polynomial in n,
  40. as we figured out before.
  41. Now what about the program?
  42. So for the program, we said that,
  43. of course the size of the program of the algorithm
  44. does not change with the size of the input,
  45. so if you look at the program and your write it
  46. as we said, we've written the code from left to right,
  47. but normally, you'll write it from top to bottom,
  48. so if you took this code and wrote it like this,
  49. then you would have a constant number of lines in your program
  50. and that would be a certain position on where you are,
  51. so again here,
  52. there's a constant number of potential positions where you can be in the code,
  53. and of course, you just have one code,
  54. so there's no polynomial size here.
  55. It's just a constant number of code lines.
  56. And finally, over here fr the input;
  57. of course this is read only, but what I'm interested in
  58. is again the possible number of states
  59. that you can have in each of these memory cells,
  60. and that again is the same constant as over here,
  61. and here we have again a polynomial in n,
  62. so what does this have to do with the Boolean formula that I just showed you?
  63. Well, what we could do is turn this into a Boolean formula
  64. with a huge number of variables,
  65. but you will see that the number of variables is still polynomial.
  66. So what are my variables going to be?
  67. I'm going to have one variable
  68. for each of those black boxes here
  69. and also one variable for each of these here,
  70. and so on, and so on, and so on.
  71. I'm going to have
  72. one variable for all of the possibilities
  73. where I could be in my program code,
  74. and again here I'm going to do the same thing as I did here on the left side.
  75. I will have one Boolean variable
  76. for each of those possibilities,
  77. and what one of those Boolean variables means is
  78. basically--or what I want it to mean is
  79. if it's set to true,
  80. it tells me that
  81. a memory cell contains that value,
  82. so if this variable here is set to true,
  83. I want that memory cell up here to contain the value 0.
  84. If it's set to 1, I want this one here to contain the value 1.
  85. If it's set to 2, I want this one here to have the value 2, and so on.
  86. And now you see why the Boolean formula that I just showed you
  87. where you can force just exactly one single variable to be true
  88. is useful in this case,
  89. because if I put all of these variables here
  90. into such a Boolean formula,
  91. I would have a Boolean formula that can be satisfied
  92. if and only if
  93. exactly one of those variables here is true,
  94. so it tells me
  95. uniquely what goes into this memory cell here
  96. as long as it's satisfied,
  97. and the same thing over here, and over here, and over here.
  98. And now
  99. if I write this Boolean formula for this memory cell here,
  100. I write it for this memory cell here, here of course also,
  101. and so on,
  102. and if I combine all of those Boolean formulas,
  103. so I have a Boolean formula here,
  104. I have a Boolean formula here,
  105. I have one here,
  106. from this column,
  107. from this column,
  108. from this column, and so on.
  109. So I have Boolean formula,
  110. and then I do an and,
  111. and I have the next Boolean formula, and I have an and,
  112. and I have the next Boolean formula,
  113. and I continue doing this, and I will also do this here for the program.
  114. And of course, I will get a very, very, very large Boolean formula.