## ← Preprocessing For SAT - Intro to Theoretical Computer Science

• 2 Followers
• 20 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=Y6vpmGdYxXU" data-team="udacity"></div> ``` 1 Language

Showing Revision 2 created 05/25/2016 by Udacity Robot.

1. So let's have a look. What about x1? So here we have x1, not x1, not x1 and x1.
2. I have no idea what to do with that, so it's probably not easy.
3. What about x2? So here we have x2, x2, not x2, still kind of difficult to see if we should set it to false,
4. making this clause here satisfied or if we should set it to true, satisfying those two clauses up here.
5. It's not easy, or at least it's not doable without playing around with other true or false assignment.
6. What about x3, same case? So here we have x3, not x3, x3, again, x3, not x3, no idea what to do with that.
7. So all that remains is x4. Now, where does x4 appear? X4 appears here and x4 appears here.
8. And what you'll notice is that both time we have not x4. So x4 could appear in two forms, right?
9. So x4 could appear as x4, or as not x4. But we have just this one form appearing.
10. And this goes back to the answer of the previous quiz, where I gave you an intuition for what makes SAT hard.
11. What makes SAT hard is that, if you choose a truth assignment of true or false, then some clauses obviously
12. become satisfied, but in other clauses you get less variables to satisfy that clause.
13. However, if you have a variable that just appears in one form, then you don't have that dilemma.
14. It's always clear that we should set x4, which is the correct answer here, to false, because then we satisfy this clause here,
15. we satisfy this clause here, but there are no secondary effects again. So all of the other clauses are unaffected by
16. how we set x4. So we just choose it to our advantage. And of course, also, this is something that is easy to do algorithmically.
17. So for each of the variables that appear in a Boolean formula, an algorithm could just go through
18. and see if that variable appears in both forms--so as the variable itself and in the "not" form.
19. And if it appears just in one form, then we already know how to set it. So we have now found a third pre-processing rule for SAT.
20. Now, let's step back a little bit and look at the general requirements of pre-processing.