English subtitles

← 11-04 Laws Of NP-Completeness

Get Embed Code
1 Language

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

  1. How can you deal with an NP complete problem other than avoiding it.
  2. Well, I think you should think of yourself as kind of a lawyer who has to work with the
  3. laws of NP completeness and the main law of NP completeness is this, unless P=NP,
  4. there will be no polynomial time algorithm for your NP complete problems.
  5. Now, what do good lawyers do with the law.
  6. They find loopholes and that is exactly what we are going to do for this law of NP completeness,
  7. and we're actually be looking at two loopholes.
  8. The loophole that we will be exploring in this unit is using intelligent exponential time algorithms.
  9. We're going to work in exponential time but we're going to do it in a smart way.
  10. We're going to avoid things like 2^n or 3^n, but rather we're going to have algorithm set
  11. for example I have something like 1.3^n, which is already much better
  12. and works for many practical cases.
  13. What we are then going to look at in the next units is what I like to call sloppy solutions.
  14. For all proofs of NP completeness, we always require the computer
  15. to provide the exact answer to our problem.
  16. One chance to circumvent NP completeness might be to say,
  17. "Well, we do not want the best possible solution, but we're happy with say
  18. one that is close to optimal" or for a decision problem for example, we might be saying,
  19. "Well, it's okay if we get the right answer in about 80% of the time."
  20. For each of these approaches, we will discuss the main ideas and also of course,
  21. give you some examples to make them more clear and talk a bit about the theory
  22. behind these approaches because these are techniques where you really have
  23. to understand the theory if you want to be successful in practice.
  24. So let's start out with smart exponential time algorithms.