## 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:
English
Team:
Udacity
プロジェクト：
CS313 - Theoretical Computer Science
Duration:
04:01
 Udacity Robot edited 英語(米国) subtitles for Preprocessing - Intro to Theoretical Computer Science sp1 added a translation

# English subtitles

## 改訂 Compare revisions

• API
Udacity Robot
• sp1