Got a YouTube account?

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

English subtitles

← 05-07 How To Show Intractability Solution

Get Embed Code
1 Language

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

  1. The answer here, although it might be a little bit subjective,
  2. but I think it's rather objective actually is that
  3. in terms of difficulty, it's much easier to just gather evidence
  4. than accomplish a mathematical proof in my opinion.
  5. The reason for that is that in a mathematical proof you cannot only say
  6. well these 10 people or these 20 people haven't found a good algorithm for my problem,
  7. but you would really have to show that any algorithm that anybody could ever come up with
  8. would still require exponential time which does not allow you to give any examples
  9. or just state the number of algorithms, but you have to go about it in another way
  10. that is much more complicated as you'll also see in this unit.
  11. In terms of convincing this of course, the mathematical proof is more convincing
  12. than just gathering evidence because here we know that no matter what happens
  13. the problem is intractable whereas here we could just have another smart person coming in
  14. who finds a polynomial time algorithm and then it suddenly turns out that the problem is tractable.