English subtitles

← 04-11 Tractable And Intractable Problems

Get Embed Code
1 Language

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

  1. What both Alice and Bob have so far been able to find is--they have found
  2. exponential time algorithms for their problem and they haven't been able
  3. to come up with anything better so far.
  4. The question of course is does the fact that Alice and Bob have not yet been able to come up
  5. with a polynomial time algorithm mean that the problems they are working on are only solvable
  6. in exponential time or could there be some sort of polynomial time algorithm
  7. that they haven't found yet and there's a special terminology for that.
  8. Problems or computer problems where you only have exponential time algorithms
  9. are called intractable problems, and those compute problems where you can't find
  10. a polynomial time algorithm--those are called tractable problems.
  11. And this is going to be a rather obvious question to some of you I hope--
  12. does the fact that so far we only know exponential time algorithms for the problem that
  13. Alice was working on and the problem that Bob was working on.
  14. Does that mean that their problems are intractable or in other words, can we already say
  15. whether Alice's or Bob's problems are intractable or tractable, and I would like you to tell me
  16. if you think that is the case, so if we can already say that their problems are intractable
  17. or if there's probably more information that we need.