English subtitles

← 19-05 What You Know - NP

Get Embed Code
1 Language

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

  1. And again, that is probably very familiar to you by now.
  2. NP is is the complexity class of all problems that can
  3. that can be solved in polynomial time
  4. or in non-deterministic RAM.
  5. That's what the N here stands for; now you might have found this
  6. quiz rather easy, but actually that you're so familiar with P and NP
  7. I think it's something special,
  8. because I find that not many people actually understand what
  9. P and NP stand for, and what the difference is between the two.
  10. Now if you really want to impress a theoretical computer scientist,
  11. of course you have to be a little bit nit picky.
  12. First of all, P and NP formally are
  13. defined for decision problems,
  14. so here we said all problems, but actually,
  15. if you're very formal, it's only for decision problems,
  16. and the other thing is that
  17. originally, those classes were not defined on the
  18. RAM but rather on a computer model
  19. known as a Turing machine,
  20. named after the computer pioneer, Alan Turing.
  21. Now having a precise definition doesn't really change anything about P and NP
  22. the way that we were talking about it,
  23. but when you get down into the details of these classes,
  24. it might actually matter that you have a Turing machine here
  25. instead of a RAM and that you're talking about decision problems
  26. instead of optimization problems.
  27. But for here, I think it's just fine to think of it as the
  28. complexity class of all problems
  29. that can be solved in polynomial time
  30. on a deterministic or non deterministic RAM.