Got a YouTube account?

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

English subtitles

← 09-14 Should You Try To Solve P Vs NP?

Get Embed Code
1 Language

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

  1. Now, the question of course is should you try to solve P versus NP?
  2. There's a web page called the P versus NP page
  3. and that page lists a lot of re-attempts that have been made to settle the P versus NP question.
  4. The list which you find on this web page as you can see is very, very, very long.
  5. The list contains almost a hundred papers, of which when I checked that the last time,
  6. 41 claimed that P equals NP and 46 claimed that P does not equal NP.
  7. So, we already know that half of these proofs are wrong,
  8. but of course, none of them is accepted in any way.
  9. None of them has ever been published in a scientific journal so we can almost safely assume
  10. that proofs not these papers all claim to have do not hold up against scientific scrutiny
  11. and some of those proofs are actually quite huge.
  12. For example, there was a recent attempt to show that P does not equal NP
  13. which used up 102 pages which is almost a full Udacity course
  14. and you know why it didn't work out, a flaw on page 67
  15. and it is for these reasons that, in fact, many computer scientist
  16. will nowadays refuse to even look at your proof of P equals NP or P does not equal NP
  17. unless you can convince them that you have a new insight that hasn't been discussed before.
  18. So, the status of P versus NP is this.
  19. Despite over 40 years of research and a million dollar price
  20. and many computer science heavyweights having attempted to resolve P versus NP
  21. so far there've been no solution and that has even been shown
  22. and unfortunately, we can't go deeper into that,
  23. that some common mathematical tools that are used in theoretical computer science
  24. are not capable of solving this question.
  25. So, not only do you need to have a good idea for proof,
  26. but you also need to invent new techniques for theoretical computer science.
  27. So, I do not want to discourage you from thinking about P versus NP,
  28. but don't quit your day job to attempt to resolve this question.
  29. So, let's do our final quiz in this unit.
  30. Under what circumstances should you try to settle the P versus NP question?
  31. Is it when you think who had a brilliant insight.
  32. Is it when you had a brilliant insight and you have made sure that this hasn't been tried before
  33. Or is it when you have a brilliant insight that you have made sure that no one has tried before
  34. and you know that your proof technique is actually capable of settling the P versus NP question
  35. Or is it when you are a seasoned and respected computer scientist with nothing to lose
  36. and enough money or savings to sustain yourself
  37. So, please check all of the correct ones.