## ← 09ps-05 Satisfaction Guaranteed

• 1 Follower
• 30 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=52QyFTiepR8" data-team="udacity"></div> ``` 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.