English subtitles

← 10-33 Number Of Vertices For Variables

Get Embed Code
1 Language

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

  1. We started with an input to SAT,
  2. and that is going to be a lean formula with n variables
  3. and these are going to be as always x₁, x₂ and so on until you reach xn.
  4. And we are also going to specify the number of clauses
  5. and I'm just going to use the letter m here
  6. so we're going to say we have m clauses
  7. and I'm also going to give them names
  8. so I'm going to call them C₁, C₂ and so on until you reach Cm.
  9. We're now going to construct a graph that represents or encodes this Boolean Formula here
  10. and we are going to do this just as we have done before.
  11. So, this part here is going to represent X₁.
  12. This part over here is going to represent X₂ and so on and this one here Xn.
  13. Now, the question of course is how long these parts for each X need to be,
  14. and that depends on the number of clauses
  15. because we're going to attach clauses to the variables here.
  16. In order to make this safe, we should construct this part
  17. so that we have m of these edge crossings here
  18. because then we know that for each clause we have an edge
  19. where we can attach that clause to.
  20. Now, if we have m of these crossings here
  21. this means that we have m+1 of these groups of three vertices here
  22. so we have 3(m+1) vertices in this part here
  23. and then we have one more vertex here, one more vertex here
  24. so +2 if we extended like this, and this holds true for all of the other parts here as well.
  25. Now, for each clause but of course also going to add a vertex like so
  26. and again this vertex here is going to represent clause 1
  27. this vertex here is going to represent clause 2 and so until we get to clause m.
  28. My first question for you is
  29. how many vertices are we using to represent the variables
  30. so to represent x₁, x₂ and so on until we get to xn
  31. and I would like you to enter this as four numbers
  32. and so it's going to be some number times n plus some number times m
  33. plus some number times mn plus possibly some constant.
  34. Please give me these four numbers here
  35. to correctly count the number of vertices that we have here to represent variables.