English subtitles

← 08-06 Properties Of Boolean Formula

Get Embed Code
1 Language

Download

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

  1. And this is, I promise, going to be the most
  2. complicated part of this unit.
  3. Once you've understood this,
  4. you have understood how to prove the Cook-Levin theorums,
  5. so bear with me for another minute here.
  6. If we write this huge Boolean formula
  7. what I would like to ask you now is
  8. what properties this Boolean formula has.
  9. So if I write a big Boolean formula like this here,
  10. so the train that's exactly one variable here
  11. is set to true one here, one here, and so on and so on.
  12. What I would like you to think about is
  13. some of the properties that this Boolean formula will have.
  14. So there are 3 properties of 3 choices that I'm giving you.
  15. One is that the size of this Boolean formula here is polynomial in in.
  16. The second one is
  17. that this Boolean formula here has only a single satisfying assignment.
  18. And the third one is that every satisfying assignment
  19. of this Boolean formula
  20. presents a potential snapshot,
  21. so it kind of uniquely defines what the memory of the RAM looks like
  22. and where the program is at.
  23. Now of course, there's only 3 choices here;
  24. again, more than 1 can be true and you could
  25. make your way through by guessing,
  26. but before that, I'd encourage you to think through these statements,
  27. because once you understand this part,
  28. the rest of the Cook-Levin theory is actually quite easy.