## Requirements For Preprocessing Solution - Intro to Theoretical Computer Science

• 0:00 - 0:04
So I think there's two things that are true here. The first one is polynomial time,
• 0:04 - 0:10
because we're trying to do pre-processing for problems that normally require exponential time.
• 0:10 - 0:14
So if we don't have this requirement here, you could use pre-processing to already solve the problem,
• 0:14 - 0:19
because then you would have exponential time. And that really wouldn't make any sense.
• 0:19 - 0:25
Of course, in practice it could make sense to have certain exponential time pre-processing algorithms where,
• 0:25 - 0:29
for example, the base of the exponent is much smaller than of the general algorithm.
• 0:29 - 0:33
But actually I've never seen that done. And right now, for us, polynomial time is a good requirement to have.
• 0:33 - 0:41
Speeding up worse-case running time is, in my opinion, not a requirement for pre-processing.
• 0:41 - 0:46
Of course, you would like to get a speed-up, but on the other hand, as you've seen, the pre-processing rules are very simple.
• 0:46 - 0:51
So, we might always encounter instances where pre-processing does not apply.
• 0:51 - 0:56
But that doesn't mean we shouldn't do it. Pre-processing runs in polynomial time, so it's easy to do.
• 0:56 - 1:00
So we should just hope that pre-processing helps us, but not make it a requirement.
• 1:00 - 1:07
And finally, that is of course very important. Pre-processing must not affect the solution that we get in the end.
• 1:07 - 1:13
If we have a decision problem where the answer is yes or no, after pre-processing, we want the answer to be the same, of course.
• 1:13 - 1:19
And the same is for optimization problems. If the answer is 10, 11 or 12, then after pre-processing,
• 1:19 - 1:25
the answer should remain 10, 11 or 12. Because otherwise, pre-processing would actually alter the problem,
• 1:25 - 1:30
and it would alter the solution to that problem, which of course is something we do not want.
タイトル：
Requirements For Preprocessing Solution - Intro to Theoretical Computer Science
Video Language:
English
Team:
Udacity
プロジェクト：
CS313 - Theoretical Computer Science
Duration:
01:30
 Udacity Robot edited 英語(米国) subtitles for Requirements For Preprocessing Solution - Intro to Theoretical Computer Science sp1 added a translation

# English subtitles

## 改訂 Compare revisions

• API
Udacity Robot
• sp1