• The Amara On Demand team is looking for native speakers of German, Japanese, Korean, Italian, Hindi and Dutch to help with special paid projects
Apply here Hide

## ← 09ps-06 Satisfaction Guaranteed Solution

• 1 Follower
• 32 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=qO9ZR5BUAqg" data-team="udacity"></div> ``` 1 Language

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

1. Alright, first if we had a complete series of snapshots
2. from a nondeterministic RAM solving SAT on his formula.
3. Well, a nondeterministic RAM can solve SAT in polynomial time,
4. so we can check those in polynomial time as well
5. since we just have a list of these.
6. So once we have those, we can definitely verify that his formula is satisfiable.
7. Now if we had a list of satisfiable clauses,
8. this actually isn't enough to verify that Bob's formula is also satisfiable.
9. To see this, let's take a look at the formula in somewhat pythonic form,
10. X and not X.
11. Now clearly X is a satisfiable clause and so is not X,
12. but the entire Boolean formula is definitely not satisfiable.
13. So a list of satisfiable clauses actually isn't enough
14. for us to believe Bob.
15. Now if we had a satisfying assignment for all of the variables in the formula,
16. then sure, we can just plug them into the formula
17. and check on a deterministic RAM,
18. and that occurs in polynomial time.
19. Similarly, if add all calls to if_better on the Boolean formula,
20. well, if_better is the only difference
21. between a nondeterministic and a deterministic RAM,
22. so if we had all the calls to if_better,
23. we wouldn't actually have to simulate if_better,
24. we would know what the algorithm did at each step of the process.
25. So we could also check Bob's formula using just this.
26. Not even a complete series of snapshots is necessary
27. just the calls to if_better.
28. Now let's say we had a satisfying assignment for 90% of the variables.
29. Well, 90% of the variables still leaves 10%,
30. and 10% of exponential is, well, exponential.
31. So we would still have exponentially many variables to check.
32. So this actually doesn't work.