 ## ← 06-06 Complexity Classes

• 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=S22epL5mSXs" data-team="udacity"></div> ``` 1 Language

• English [en]

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

1. So now with that kind of magic function if-better we could solve all the three problems
2. we have looked at so far in polynomial time.
3. We could solve vertex cover, we could solve independent set,
4. and we could solve clique in polynomial time.
5. Now theoretical computer scientists like to divide problems into so-called complexity classes.
6. And a complexity class basically contains all problems that can be solved
7. on a given machine within a specified time or a specified memory or even both.
8. But we're going to stick with time for now.
9. So if we draw this as a matrix and put time here and the machine here
10. then so far we learned about two different types of time.
11. We have learned about polynomial time and we have learned about exponential time,
12. and we have the normal RAM, the model that has basically the same capabilities as any computer
13. that you know, and we have just learned about the RAM that has the if-better function available.
14. Each of these fields here in the matrix is a complexity class.
15. So this field here, for example, would contain all problems that can be solved
16. in exponential time on a normal RAM.
17. So vertex cover, independent set, and clique would all be contained in this class.
18. But of course they can also be contained in other classes and I would actually like you
19. to figure this out as our next quiz and the question is,
20. in which other complexity classes, so this one here, this one here, or this one here,
21. can we put our three problems vertex cover, independent set, and clique?
22. And I would like you to make a check mark if you're sure
23. that we can put these problems into that complexity class.
24. If you're sure that we cannot do that or if we're not certain, I want you to leave that field blank.