English subtitles

← 04-15 Tractable Vs Intractable

Get Embed Code
1 Language

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

  1. Now, we already talked about the notion of polynomial running time
  2. being associated with tractability and exponential running time being associated with intractability
  3. can lead to some borderline cases where you would probably argue.
  4. For example, if you had an algorithm that had polynomial running time of O(n¹⁰)
  5. and you had an exponential running time algorithm with running time 1.01^n,
  6. then actually it would be very hard to decide which one of these algorithms to take.
  7. It would kind of depend on additional information.
  8. What other constant factors here and what is the size of the n.
  9. As I mentioned before, this hardly occurs in practice and this hardly occurs in practice as well.
  10. Tractable problems are usually really tractable
  11. and intractable problems tend to be intractable in general,
  12. but in later units, we'll actually see how you can deal with exponential running times.
  13. The question we're now dealing with is both for Alice's problem and Bob's problem.
  14. Are they intractable or can we find a polynomial time algorithm
  15. that would show us that these problems are tractable?
  16. So far Alice and Bob really don't have a good idea on how to tackle that problem.
  17. That's why they actually decides to get together
  18. and discuss with each other the problems that they are trying to solve,
  19. and to that meeting, they also invites a friend of theirs,
  20. and that friend of theirs is Carol because as they have learned
  21. Carol is also working on a problem that so far she has only found an exponential time algorithm for.