English subtitles

← 14-01 Introduction

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. In the last unit, we have talked about what you can do when a problem is NP-complete,
  2. despite it being NP-complete.
  3. And we have found out that there are techniques such as optimized search trees,
  4. preprocessing, and fixed parameter tractability
  5. that you can often use to solve NP-complete problems and practice
  6. despite their hardness in general.
  7. So what can we do when these techiniques don't work,
  8. and we don't want to prove that P=NP?
  9. Well, in that case, we can try something else.
  10. We can try to give our algorithm a little leeway.
  11. So instead of demanding that the algorithm finds the best possible solution,
  12. we'll allow the algorithm to find a solution that is within a certain range of the best possible solution.
  13. In return, of course, we'll demand from our algorithm that it runs in polynomial time.