Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Requirements For Preprocessing Solution - Intro to Theoretical Computer Science

Get Embed Code
1 Language

Showing Revision 2 created 05/25/2016 by Udacity Robot.

  1. So I think there's two things that are true here. The first one is polynomial time,
  2. because we're trying to do pre-processing for problems that normally require exponential time.
  3. So if we don't have this requirement here, you could use pre-processing to already solve the problem,
  4. because then you would have exponential time. And that really wouldn't make any sense.
  5. Of course, in practice it could make sense to have certain exponential time pre-processing algorithms where,
  6. for example, the base of the exponent is much smaller than of the general algorithm.
  7. But actually I've never seen that done. And right now, for us, polynomial time is a good requirement to have.
  8. Speeding up worse-case running time is, in my opinion, not a requirement for pre-processing.
  9. 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.
  10. So, we might always encounter instances where pre-processing does not apply.
  11. But that doesn't mean we shouldn't do it. Pre-processing runs in polynomial time, so it's easy to do.
  12. So we should just hope that pre-processing helps us, but not make it a requirement.
  13. And finally, that is of course very important. Pre-processing must not affect the solution that we get in the end.
  14. 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.
  15. And the same is for optimization problems. If the answer is 10, 11 or 12, then after pre-processing,
  16. the answer should remain 10, 11 or 12. Because otherwise, pre-processing would actually alter the problem,
  17. and it would alter the solution to that problem, which of course is something we do not want.