[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.03,0:00:07.33,Default,,0000,0000,0000,,So cleaning the input, which is more technically also known as pre-processing--what's the idea behind that?
Dialogue: 0,0:00:07.33,0:00:12.07,Default,,0000,0000,0000,,Here's what you would normally do for an NP-complete problem as we have talked about so far:
Dialogue: 0,0:00:12.07,0:00:18.97,Default,,0000,0000,0000,,So if you're given the input for an NP-complete problem. What you would do using the techniques from the previous units
Dialogue: 0,0:00:18.97,0:00:22.97,Default,,0000,0000,0000,,is you would fire up your search tree to try and find an optimal solution.
Dialogue: 0,0:00:22.97,0:00:27.90,Default,,0000,0000,0000,,And of course, that search tree has exponential size. So the algorithm goes through that tree here
Dialogue: 0,0:00:27.90,0:00:34.57,Default,,0000,0000,0000,,until, at a certain point in time, it says, "Bingo, I found a solution," or, "I found the best possible solution."
Dialogue: 0,0:00:34.57,0:00:41.37,Default,,0000,0000,0000,,The idea of pre-processing now is similar to something that we already saw for vertex cover or independent set,
Dialogue: 0,0:00:41.37,0:00:47.03,Default,,0000,0000,0000,,where, for certain vertices, while we were traversing the search tree, or even in advance,
Dialogue: 0,0:00:47.03,0:00:54.50,Default,,0000,0000,0000,,what we could already say for certain vertices, we know what assignment that vertex is going to have in an optimum solution.
Dialogue: 0,0:00:54.50,0:00:59.93,Default,,0000,0000,0000,,And we could make that statement without actually going through any branching, but in polynomial time.
Dialogue: 0,0:00:59.93,0:01:06.83,Default,,0000,0000,0000,,And that is the idea of pre-processing. The idea of pre-processing is, if you can actually find certain parts of the input,
Dialogue: 0,0:01:06.83,0:01:15.67,Default,,0000,0000,0000,,where in polynomial time, of course, you can already say how they would be handled in an optimum solution.
Dialogue: 0,0:01:15.67,0:01:21.87,Default,,0000,0000,0000,,So we're kind of nibbling away at the input here. And what that, of course, means is if your pre-processing is successful,
Dialogue: 0,0:01:21.87,0:01:29.50,Default,,0000,0000,0000,,or especially if it's very successful, then the search tree that results from that input is not going to be as big.
Dialogue: 0,0:01:29.50,0:01:34.43,Default,,0000,0000,0000,,So there's certain parts of the search tree that you don't have to do, because you already have found out
Dialogue: 0,0:01:34.43,0:01:38.47,Default,,0000,0000,0000,,in the pre-processing what that part of the solution is going to look like.
Dialogue: 0,0:01:38.47,0:01:44.53,Default,,0000,0000,0000,,So the search tree size will decrease. So we can, for example, cut off this branch here, because we've already
Dialogue: 0,0:01:44.53,0:01:49.67,Default,,0000,0000,0000,,pre-processed this, and we can cut off this one here because we also pre-processed that one.
Dialogue: 0,0:01:49.67,0:01:52.67,Default,,0000,0000,0000,,So now let's make this more concrete, and let me give you a concrete example.
Dialogue: 0,0:01:52.67,0:01:58.67,Default,,0000,0000,0000,,And we're going to do this for SAT, because SAT is a problem where pre-processing is usually very successful.
Dialogue: 0,0:01:58.67,0:02:05.30,Default,,0000,0000,0000,,So if you were, for example, to use a commercial SAT solver, then pre-processing will play a very very important role in that.
Dialogue: 0,0:02:05.30,0:02:11.87,Default,,0000,0000,0000,,I once talked to somebody who develops those solvers, and they basically said that his package works 90-95%
Dialogue: 0,0:02:11.87,0:02:19.17,Default,,0000,0000,0000,,through pre-processing. So even for SAT instances with thousands of variables, his package can basically solve it,
Dialogue: 0,0:02:19.17,0:02:23.57,Default,,0000,0000,0000,,but it can only solve it because the pre-processing algorithms are very good.
Dialogue: 0,0:02:23.57,0:02:31.27,Default,,0000,0000,0000,,So you'll remember that SAT was the problem of finding if a given Boolean formula has a satisfying assignment or not.
Dialogue: 0,0:02:31.27,0:02:35.77,Default,,0000,0000,0000,,And I'm now going to write down a Boolean formula for you, and then we're going to do a little quiz
Dialogue: 0,0:02:35.77,0:02:38.77,Default,,0000,0000,0000,,to make pre-processing more concrete.
Dialogue: 0,0:02:38.77,0:02:48.67,Default,,0000,0000,0000,,So the SAT formula is x1 or x3 or x5, and not x1 or x2 or x4, and so on, and so on.
Dialogue: 0,0:02:48.67,0:02:53.07,Default,,0000,0000,0000,,Now, of course this formula here doesn't have very many variables. It's just six variables--
Dialogue: 0,0:02:53.07,0:03:01.43,Default,,0000,0000,0000,,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
Dialogue: 0,0:03:01.43,0:03:06.47,Default,,0000,0000,0000,,has a satisfying assignment or not. But of course, what we want to do now is pre-processing,
Dialogue: 0,0:03:06.47,0:03:12.57,Default,,0000,0000,0000,,And that means that we want to see if, for certain variables, in this Boolean formula, we can figure out
Dialogue: 0,0:03:12.57,0:03:18.13,Default,,0000,0000,0000,,if they should be set to true or false, without actually trying all possible combinations.
Dialogue: 0,0:03:18.13,0:03:23.73,Default,,0000,0000,0000,,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,
Dialogue: 0,0:03:23.73,0:03:33.53,Default,,0000,0000,0000,,and then consider the variables x1, x2, x3 and x4, and for each of those variables, determine if it's easy to see,
Dialogue: 0,0:03:33.53,0:03:38.33,Default,,0000,0000,0000,,if they should be set to true or false. And by easy, I mean without actually trying around different true assignments
Dialogue: 0,0:03:38.33,0:03:44.70,Default,,0000,0000,0000,,for the other variables, but you can basically immediately say, for these variables, if they should be set to true or false.
Dialogue: 0,0:03:44.70,0:03:50.83,Default,,0000,0000,0000,,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--
Dialogue: 0,0:03:50.83,0:03:59.97,Default,,0000,0000,0000,,I think that for two of these variables here, it's rather easy to see. And I would like you to select those two.