YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 09ps-05 Satisfaction Guaranteed

Get Embed Code
1 Language

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

  1. Let's say we have a friend Bob.
  2. Bob is blue, he's had a nasty run in with a can of paint.
  3. Now let's assume that Bob has a Boolean formula,
  4. not necessarily this one but just some Boolean formula.
  5. And suppose Bob comes to us and tells us I've already
  6. found out that this Boolean formula is satisfiable.
  7. Now let's say we don't necessarily trust Bob.
  8. Bob is given to exaggeration.
  9. We'd like to be able to figure out in polynomial time
  10. whether or not Bob is telling us the truth.
  11. So how would be go about doing that?
  12. Let's say Bob came to us with a complete series of snapshots
  13. from a nondeterministic RAM solving SAT on his formula.
  14. Would that be enough for us to believe that he had a satisfiable formula?
  15. How about if he had a list of satisfiable clauses?
  16. For example, he had a list that had x as the satisfiable clause
  17. and not Y as a satisfiable clause.
  18. Then for the entire Boolean formula,
  19. could we then determine whether it was satisfiable or not?
  20. What about if you had a satisfying assignment for all
  21. of the variables in the formula?
  22. What if we had all the calls to if_better on the Boolean formula?
  23. So not necessarily a complete series of snapshots
  24. from a nondeterministic RAM solving SAT on his formula,
  25. but just all the calls to if_better.
  26. Would that be enough for us to believe Bob?
  27. And finally, what if we had a satisfying assignment
  28. for not all the variables but 90% of the variables in Bob's formula.
  29. Could we believe him then?
  30. Please check all that apply.