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

1. Title:
   10-33 Number Of Vertices For Variables
2. Description:

3. 0 0:00 - 0:02
   We started with an input to SAT,
4. 2050 0:02 - 0:07
   and that is going to be a lean formula with n variables
5. 7020 0:07 - 0:13
   and these are going to be as always x₁, x₂ and so on until you reach xn.
6. 12740 0:13 - 0:15
   And we are also going to specify the number of clauses
7. 15400 0:15 - 0:17
   and I'm just going to use the letter m here
8. 17290 0:17 - 0:19
   so we're going to say we have m clauses
9. 19200 0:19 - 0:21
   and I'm also going to give them names
10. 21100 0:21 - 0:27
    so I'm going to call them C₁, C₂ and so on until you reach Cm.
11. 27320 0:27 - 0:33
    We're now going to construct a graph that represents or encodes this Boolean Formula here
12. 33210 0:33 - 0:36
    and we are going to do this just as we have done before.
13. 36120 0:36 - 0:40
    So, this part here is going to represent X₁.
14. 39730 0:40 - 0:46
    This part over here is going to represent X₂ and so on and this one here Xn.
15. 45720 0:46 - 0:51
    Now, the question of course is how long these parts for each X need to be,
16. 51320 0:51 - 0:54
    and that depends on the number of clauses
17. 53660 0:54 - 0:57
    because we're going to attach clauses to the variables here.
18. 57150 0:57 - 1:00
    In order to make this safe, we should construct this part
19. 60340 1:00 - 1:05
    so that we have m of these edge crossings here
20. 64790 1:05 - 1:09
    because then we know that for each clause we have an edge
21. 68590 1:09 - 1:11
    where we can attach that clause to.
22. 70610 1:11 - 1:14
    Now, if we have m of these crossings here
23. 74010 1:14 - 1:21
    this means that we have m+1 of these groups of three vertices here
24. 80770 1:21 - 1:27
    so we have 3(m+1) vertices in this part here
25. 87070 1:27 - 1:30
    and then we have one more vertex here, one more vertex here
26. 90400 1:30 - 1:36
    so +2 if we extended like this, and this holds true for all of the other parts here as well.
27. 96090 1:36 - 1:40
    Now, for each clause but of course also going to add a vertex like so
28. 100320 1:40 - 1:44
    and again this vertex here is going to represent clause 1
29. 104090 1:44 - 1:50
    this vertex here is going to represent clause 2 and so until we get to clause m.
30. 109940 1:50 - 1:52
    My first question for you is
31. 111640 1:52 - 1:55
    how many vertices are we using to represent the variables
32. 114770 1:55 - 1:58
    so to represent x₁, x₂ and so on until we get to xn
33. 118460 1:58 - 2:01
    and I would like you to enter this as four numbers
34. 120550 2:01 - 2:06
    and so it's going to be some number times n plus some number times m
35. 125950 2:06 - 2:13
    plus some number times mn plus possibly some constant.
36. 132520 2:13 - 2:14
    Please give me these four numbers here
37. 134280 2:14 -
    to correctly count the number of vertices that we have here to represent variables.