## ← 11-04 Laws Of NP-Completeness

• 1 Follower
• 24 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=iEAxaAqEe68" data-team="udacity"></div> ``` 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.