YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 01-06 Computability Or Complexity Theory Solution

Get Embed Code
1 Language

Showing Revision 2 created 02/06/2019 by Michel Smits.

  1. And, of course, there's going to be
    more challenging quizzes here,

  2. but for a warmup I think it is very good
    to understand the difference
  3. between computability
    and complexity theory.
  4. The first question, how fast a computer
    can find a way between 2 points on a map,
  5. belongs in complexity theory because
    here it's a question of resources.
  6. So "how fast," that is a question about
    the time that a computer needs,
  7. and therefore, investigating this question
    belongs in complexity theory.
  8. Asking if a program can decide
    if another program is malware,
  9. that belongs in computability
    because we are not asking
  10. about any resources,
    we're just if it's possible in principle.
  11. We're asking, "Can a program do that?"
  12. We're not asking how fast or
    with how much memory it can do that.
  13. In the third question we are,
    again, asking about resources.
  14. We're asking about how much memory,
    and therefore, this 1 belongs in complexity theory.
  15. The question about memory is something
    we are not going to look at much in this course.
  16. Actually, I think we are not
    going to look at it at all.
  17. We're going to be
    concerned mostly with time,
  18. how fast a computer can
    solve a given problem,
  19. and, toward the end of this unit,
  20. we are going to pose
    the ultimate resource question
  21. and ask, "What are the limits
    of computation in general?