English subtitles

← P=NP - Intro to Algorithms

Get Embed Code
3 Languages

Showing Revision 3 created 05/24/2016 by Udacity Robot.

  1. This brings us to a point where we can ask one of the most fundamental questions in theoretical
  2. computer science and that is does P=NP and in particular, here's what we actually know.
  3. This is true. We know that every problem that's in P is in NP and every problem that is NP is in EXP,
  4. that is to say any problem that you can solve in polynomial time,
  5. we can certainly solve in non-deterministic polynomial time,
  6. and any problem that we can solve in a non-deterministic polynomial time,
  7. we can also solve in exponential time, but here's what we don't know.
  8. It could be the case that the class NP is actually equal to the class EXP.
  9. That is to say the set of problems that we can solve in a non-deterministic polynomial time
  10. might be exactly the same as the ones that we can solve in exponential time.
  11. So there's a sort of outer set and that's distinct from say this inner set,
  12. which is the set of problems that are solvable in polynomial time.
  13. There's one other thing that we know, we do know that there really
  14. is a difference between polynomial and exponential time.
  15. There's some problems that can be solved in exponential time that are definitely not NP.
  16. So we know those two things are different, but we don't really know.
  17. It could be that NP is equal to x. It could also that P is equal to NP.
  18. So the problems that we can solve in a non-deterministic polynomial time
  19. might be exactly the same as the ones that we can solve in polynomial time,
  20. which both would be then different from exponential time
  21. or could very well be that there are really three different categories here.
  22. That problems that are in NP don't necessarily require exponential time,
  23. but they may not be solvable in polynomial time either--we don't know.
  24. So this question of whether or not P=NP, whether we're in this case here is a pretty heavy question.
  25. So what happens if P does equal NP. Well, a lot people say a lot of different things.
  26. Let's turn this into a quiz to see what you think.
  27. So one possibility is that cryptographic protocols, so things were keeping secrets in encrypting data
  28. that are based on problems like factoring that are in NP could be cracked.
  29. Another is that there's a whole lot of computer science theoreticians
  30. who will be suddenly out of work because they will no longer be having to think about this problem.
  31. Another possible outcome might be that with P equal to NP
  32. that means the computers will be smarter than people.
  33. They will be able to solve problems fast that people can't.
  34. So I don't know, just tell me which one you think is true.