English subtitles

← 06-06 Complexity Classes

Get Embed Code
1 Language

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.