Return to Video

Preprocessing - Intro to Theoretical Computer Science

  • 0:00 - 0:07
    So cleaning the input, which is more technically also known as pre-processing--what's the idea behind that?
  • 0:07 - 0:12
    Here's what you would normally do for an NP-complete problem as we have talked about so far:
  • 0:12 - 0:19
    So if you're given the input for an NP-complete problem. What you would do using the techniques from the previous units
  • 0:19 - 0:23
    is you would fire up your search tree to try and find an optimal solution.
  • 0:23 - 0:28
    And of course, that search tree has exponential size. So the algorithm goes through that tree here
  • 0:28 - 0:35
    until, at a certain point in time, it says, "Bingo, I found a solution," or, "I found the best possible solution."
  • 0:35 - 0:41
    The idea of pre-processing now is similar to something that we already saw for vertex cover or independent set,
  • 0:41 - 0:47
    where, for certain vertices, while we were traversing the search tree, or even in advance,
  • 0:47 - 0:54
    what we could already say for certain vertices, we know what assignment that vertex is going to have in an optimum solution.
  • 0:54 - 1:00
    And we could make that statement without actually going through any branching, but in polynomial time.
  • 1:00 - 1:07
    And that is the idea of pre-processing. The idea of pre-processing is, if you can actually find certain parts of the input,
  • 1:07 - 1:16
    where in polynomial time, of course, you can already say how they would be handled in an optimum solution.
  • 1:16 - 1:22
    So we're kind of nibbling away at the input here. And what that, of course, means is if your pre-processing is successful,
  • 1:22 - 1:29
    or especially if it's very successful, then the search tree that results from that input is not going to be as big.
  • 1:30 - 1:34
    So there's certain parts of the search tree that you don't have to do, because you already have found out
  • 1:34 - 1:38
    in the pre-processing what that part of the solution is going to look like.
  • 1:38 - 1:45
    So the search tree size will decrease. So we can, for example, cut off this branch here, because we've already
  • 1:45 - 1:50
    pre-processed this, and we can cut off this one here because we also pre-processed that one.
  • 1:50 - 1:53
    So now let's make this more concrete, and let me give you a concrete example.
  • 1:53 - 1:59
    And we're going to do this for SAT, because SAT is a problem where pre-processing is usually very successful.
  • 1:59 - 2:05
    So if you were, for example, to use a commercial SAT solver, then pre-processing will play a very very important role in that.
  • 2:05 - 2:12
    I once talked to somebody who develops those solvers, and they basically said that his package works 90-95%
  • 2:12 - 2:19
    through pre-processing. So even for SAT instances with thousands of variables, his package can basically solve it,
  • 2:19 - 2:24
    but it can only solve it because the pre-processing algorithms are very good.
  • 2:24 - 2:31
    So you'll remember that SAT was the problem of finding if a given Boolean formula has a satisfying assignment or not.
  • 2:31 - 2:36
    And I'm now going to write down a Boolean formula for you, and then we're going to do a little quiz
  • 2:36 - 2:39
    to make pre-processing more concrete.
  • 2:39 - 2:49
    So the SAT formula is x1 or x3 or x5, and not x1 or x2 or x4, and so on, and so on.
  • 2:49 - 2:53
    Now, of course this formula here doesn't have very many variables. It's just six variables--
  • 2:53 - 3:01
    x1, x2, x3, x4, x5 and x6. So with a little playing around, you would probably be able to figure out if this Boolean formula here
  • 3:01 - 3:06
    has a satisfying assignment or not. But of course, what we want to do now is pre-processing,
  • 3:06 - 3:13
    And that means that we want to see if, for certain variables, in this Boolean formula, we can figure out
  • 3:13 - 3:18
    if they should be set to true or false, without actually trying all possible combinations.
  • 3:18 - 3:24
    And as I said, we're going to do this as a quiz. So what I would like you to do is to look at this Boolean formula here,
  • 3:24 - 3:34
    and then consider the variables x1, x2, x3 and x4, and for each of those variables, determine if it's easy to see,
  • 3:34 - 3:38
    if they should be set to true or false. And by easy, I mean without actually trying around different true assignments
  • 3:38 - 3:45
    for the other variables, but you can basically immediately say, for these variables, if they should be set to true or false.
  • 3:45 - 3:51
    I'm going to give you one hint for the solution, and that is that, in my opinion--and this is a bit of a subjective question--
  • 3:51 - 4:00
    I think that for two of these variables here, it's rather easy to see. And I would like you to select those two.
Preprocessing - Intro to Theoretical Computer Science
Video Language:
CS313 - Theoretical Computer Science

English subtitles

改訂 Compare revisions