Return to Video

Reduce 3-Colorability to SAT - Intro to Algorithms

  • 0:00 - 0:08
    Since 3 coloring is an NP and SAT is NP complete, meaning that it's NP hard,
  • 0:08 - 0:13
    it has to be the case that we could use SAT to solve 3 coloring problems,
  • 0:13 - 0:16
    but it's actually a little bit interesting to see how you might do that.
  • 0:16 - 0:23
    So let's take a look, here's a simple little graph and one, two, three, four nodes, four edges
  • 0:23 - 0:27
    and imagine that we want to try to 3-color this graph.
  • 0:27 - 0:31
    What we're going to do is we're going to create a ??? formula that is satisfiable
  • 0:31 - 0:36
    if and only if this graph is 3 colorable, so that it's really the same problem,
  • 0:36 - 0:40
    and the way that we're going to do that is we're going to create a bunch of boolean variables,
  • 0:40 - 0:47
    12 of them to be exact, corresponding to each of the four nodes--a, b, c, and d,
  • 0:47 - 0:50
    and for each node, we'll a boolean variable saying whether that node is
  • 0:50 - 0:54
    red or green or yellow, the three colors.
  • 0:54 - 1:01
    For example, assigning the variable a red to true, a green to false and a yellow to false
  • 1:01 - 1:06
    means that we're coloring the a node red, and so once we've assigned true values,
  • 1:06 - 1:11
    trues and falses to all 12 of these variables that corresponds perhaps to some coloring.
  • 1:11 - 1:16
    In fact, you have to be a little bit careful here because if we assigned two of these to true,
  • 1:16 - 1:20
    which is a perfectly reasonable thing to do in a boolean formula, you can't really interpret this
  • 1:20 - 1:27
    as a coloring except for may be a is orange, but that's not really allowed.
  • 1:27 - 1:37
    What we have to do now is given these 12 variables, we have to create a formula that is true
  • 1:37 - 1:46
    if and only if it corresponds to a valid coloring, meaning that both exactly one of each of these
  • 1:46 - 1:49
    triples the variables are true and there's no collisions--
  • 1:49 - 1:55
    for example, we can't have a colored red and b colored red because they're connected by an edge.
  • 1:55 - 1:58
    They will have to be different if they're connected by an edge.
  • 1:58 - 2:05
    The formula for this can be generated automatically and I'll give you glimpse at it.
  • 2:05 - 2:12
    Here it is, at least one version of it, and it's a little bit weird and complicated,
  • 2:12 - 2:16
    but it actually falls into some nice structures.
  • 2:16 - 2:25
    First there's a bunch of logic to say that it should be the case that say--
  • 2:25 - 2:30
    the a red, a green, and a yellow variables, one of them should be true.
  • 2:30 - 2:37
    If they're all false, then it's not telling us what color a should be, and it also has to be case
  • 2:37 - 2:41
    that no pair of colors can be true for a given node.
  • 2:41 - 2:45
    It can't be the case that both a red is true and a green is true, so that's bad.
  • 2:45 - 2:51
    There has to be at least one true and not the case that both a is both red and green
  • 2:51 - 2:57
    not the case that a is both red and yellow and not the case that both a is green and yellow,
  • 2:57 - 3:02
    and we do that for all four of the nodes and that tells us that
  • 3:02 - 3:07
    there's a meaningful color assignment to the nodes.
  • 3:07 - 3:10
    Then we have some additional clauses that say--
  • 3:10 - 3:14
    what can't be the case that a is red and b is red at the same time.
  • 3:14 - 3:19
    It can't be the case that a is green and b is green at the same time and it can't be the case
  • 3:19 - 3:21
    that a is yellow and b is yellow at the same time.
  • 3:21 - 3:25
    What is that saying, that saying the color--whatever the color happens to be--
  • 3:25 - 3:32
    for a it can't match the color of b and that's because they share an edge in the graph.
  • 3:32 - 3:38
    For each of the edges in the graph, we have three of these statements to rule out
  • 3:38 - 3:42
    all possible color matches, so there's three of these for one edge, two edge, three edge--
  • 3:42 - 3:45
    there's four edges in the graph so we have four blocks of these.
  • 3:45 - 3:50
    In this formula now as a whole has a satisfying assignment, has an assignment that makes
  • 3:50 - 3:56
    this whole expression true if and only if there's a coloring, a 3 coloring of that graph.
  • 3:56 - 4:00
    Now, in this case, I generated this formula by carefully looking at the graph
  • 4:00 - 4:04
    and going back and forth in making the formula, but you can automate this idea
  • 4:04 - 4:06
    by just generalizing the way that I did this here.
  • 4:06 - 4:10
    Why don't you think about how to do that and I'll ask you a question
  • 4:10 - 4:12
    just to make sure that you got the idea.
タイトル:
Reduce 3-Colorability to SAT - Intro to Algorithms
Video Language:
English
Team:
Udacity
プロジェクト:
CS215 - Intro to Algorithms
Duration:
04:13

English subtitles

改訂 Compare revisions