English subtitles

← 08-01 Algorithms To Boolean Formulae

Get Embed Code
1 Language

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

  1. So how can we take an algorithm and put that into a Boolean formula?
  2. Well, that's where Cook and Levin had another ingenious idea,
  3. because they said you can look at an algorithm
  4. running on a RAM as a series of snapshots,
  5. and what I mean by this is the following:
  6. So assume you have an algorithm on a
  7. non-deterministic RAM that runs in polynomial time,
  8. so you have a point in time T equals 0, that's when your algorithm starts out,
  9. then you have T equals 1, T equals 2, so those are the time steps here.
  10. And the final time step is going to be some polynomial of N.
  11. That is clear because we're looking at an algorithm
  12. that solves a problem that lies in NP,
  13. So that means it only takes polynomial time on a non-deterministic RAM at least.
  14. Now if you look at what happens on the RAM in each time step,
  15. I can basically draw you the following picture.
  16. If you recall from unit one what the RAM looks like,
  17. the RAM has only a few components.
  18. The RAM has a read-only memory,
  19. the RAM has a program or the algorithm running,
  20. so this algorithm here is basically the program running,
  21. and just as I would write the algorithm line by line by line,
  22. I can also write it in this way,
  23. so this here would be the first line of code,
  24. then this would be the second line of code, and so on.
  25. And finally, the RAM had a reading and writing memory,
  26. so we had some memory cells here holding the variables,
  27. and those variables, of course, are changed by the program
  28. depending on what's here in the input.
  29. And now comes the neat part that Cook and Levin observed,
  30. because what they observed is
  31. that when you look at an algorithm working on the RAM,
  32. then you can depict that as a number of these snapshots,
  33. so if you say, add T equals 0,
  34. these are the contents of the read-only memory.
  35. This is, actually we need other information,
  36. we also needs to know where the program is at,
  37. but you can basically say, this is the input here,
  38. this is the program, and this is the line of the program that we're executing right now,
  39. and this here is the contents of the read/write memory.
  40. In the beginning this will be empty,
  41. but as the algorithm works, it will also put some content in here,
  42. and then, of course, the program moves on.
  43. It can also jump back and forth here,
  44. and of course, we will have more and more content in the memory,
  45. and at a certain point in time the program will say, I'm done,
  46. and it will hopefully have a certain output here.
  47. But since we're working with decision problems,
  48. actually it's only interesting to us if the program says, yes or no at the end.
  49. So for decision problems we don't even really care about what's in here,
  50. we would care about that if we were solving the optimization problem
  51. or want additional information,
  52. but actually for a decision problem,
  53. it would just be important for us to know
  54. at which line of code the algorithm finishes.
  55. If it finishes at a return statement that will return yes to us
  56. or a return statement that will return no to us.
  57. Now let's have a closer look at those snapshots,
  58. and we'll actually do that as a quiz.
  59. So this here is one snapshot.
  60. I would like you to tell me what we can say about a single snapshot
  61. and also about all of these snapshots here.
  62. So there are 3 statements,
  63. each of which I would like you to check this box if you think they are true
  64. and otherwise leave it blank.
  65. So the first claim you could make is that each snapshot has size polynomial in N,
  66. and N is the size of the input as always.
  67. Secondly, you could claim that there can be
  68. an exponential number of snapshots if we look at all of the time steps.
  69. And finally, one claim that I would like you to check out as well is
  70. all snapshots, if taken together,
  71. so this whole part here,
  72. have polynomial size,
  73. and by polynomial size, I again mean that it's some
  74. polynomial of the input size that we're always using.
  75. You should keep in mind that the algorithm
  76. that we're looking at is an algorithm for a problem in NP,
  77. and it runs on a non-deterministic RAM.