English subtitles

← 09ps-06 Satisfaction Guaranteed Solution

Get Embed Code
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.