English subtitles

← Making a SAT graph - Intro to Algorithms

Get Embed Code
3 Languages

Showing Revision 3 created 05/24/2016 by Udacity Robot.

  1. All right, so to do the last little bit of this proof to show that 3-colorability is NP hard,
  2. we're going to show that if we had the ability to solve 3-colorability problems in polynomial time,
  3. then we could solve three SAT problems in polynomial time as well,
  4. and so what we need to be able to do to show that is if you walk up to me with any 3-CNF formula,
  5. I can quickly turn it into a 3-colorability problem, which is going to be a graph
  6. such that that graph is 3 colorable if and only if the original formula
  7. the 3-CNF formula that were given is satisfiable.
  8. So CNF here just means conjunctive normal form.
  9. It's just that form that I showed you before where the formula is the n of a bunch of clauses
  10. and each clause is the or of three literals and each literal is either variable or its negation,
  11. not the variable, so you walk up to me with 3-CNF problem,
  12. I turn that into a 3-colorability problem that can be colored if and only if the formula is satisfiable.
  13. Sounds like an interesting challenge. So let's get to it. What we're going to be doing is building a graph.
  14. We'll start off by creating some nodes with one node for every possible literal in the formula.
  15. So that's the k different variables of let's say this, just to be concrete.
  16. This formula that we come to has k variables and s clauses and we're going to add three more nodes.
  17. We'll call them true, false, and slack. I'm going to connect up the nodes initially as follows.
  18. Each literal will be connected to slack including true and false
  19. and we're going to connect true and false to each other.
  20. What that means because there's a little triangle here and
  21. we're trying see whether or not it's 3-colorable.
  22. The only way that this thing could be 3 colorable is if these three are given three different colors.
  23. So just for concreteness, let's say that the color that slack gets is red.
  24. The color that true gets is blue, true blue and the color that false gets is black, black. False won.
  25. All right, so the graph that we have so far has the property that each of these literals is
  26. going to have be colored either true or false, blue or black, if we're going to 3 color the whole graph.
  27. So that's good, that kind of make it seem like they're actually getting truth assignments.
  28. We have to be a little careful though because literal Vâ and literal not Vâ can't both be true
  29. and they can't both be false but that's an easy thing to fix in a graph colorability problem.
  30. We just connect them with an edge.
  31. So we add one edge for each variable connecting the pair of literals
  32. that can't both be true and both be false.
  33. Now what happens is the only way that we can 3 color this is if each variable is given a blue for
  34. either the variable and black for its negation or black for the variable
  35. and blue for the negation and that's like a truth assignment.
  36. A true/false assignment to that variable..
  37. So any possible truth assignment, corresponds to a 3 coloring.
  38. Any possible 3 coloring, corresponds to the truth assignment.
  39. So far we're in really good shape as far as capturing the idea of the physics of a SAT problem.