English subtitles

← 05-08 Many Solutions Vs Intractability

Get Embed Code
1 Language

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

  1. Now, before we continue, I would like to make one important point,
  2. and I don't know if this already occurred to you,
  3. but at least you might be inclined to think that it's rather obvious that
  4. the problem that Alice, Bob, and Carol are working on is intractable for one simple reason.
  5. Each of their problems has to look at an exponential number of solutions.
  6. For vertex cover, we have O(2^n) potential solutions that we have to look at
  7. because there are 2^n 0-1 assignments to the vertices
  8. for putting the vertices of a graph into a vertex cover.
  9. And the same thing is true for independent set and clique as we have seen in the last unit.
  10. Now, the question is does the fact that there is an exponential number of solutions
  11. already mean that the problem must be intractable.
  12. You could basically think this because having to consider an exponential number of solutions
  13. might mean that you have to look at each one of the solutions
  14. and that obviously is going to take exponential time.
  15. What I now want to show you is that this is not the correct intuition to have.
  16. Having many solutions does not mean that the problem is intractable.
  17. It can mean this, but it does not have to.
  18. To show you this, I'm going to give you one example
  19. where we have an exponential number of solutions
  20. but actually there is a polynomial time algorithm for our problem.
  21. What I would like you to tell me--in this graph here,
  22. how many different paths or how many different ways there are
  23. of getting from A to B if you cannot go backwards?
  24. You start out at A and once you've traveled across an edge you cannot go backwards.
  25. You always have to go forward, so how many ways are there to get from A to B?
  26. Of course this is a very simple warm up example.
  27. I'm going to draw a little arrows here just to make clear that we cannot go backwards.