Return to Video

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:
CS313 - Theoretical Computer Science

English subtitles

改訂 Compare revisions