English subtitles

← 04-12 Tractable And Intractable Problems Solution

Get Embed Code
1 Language

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

  1. The answer to that is we are not yet able to say if the problems that Alice and Bob
  2. are working on are tractable or intractable, and the reason for that is that we have only considered
  3. one single algorithm, but for a problem to be truly intractable, we would have to show that
  4. no matter what kind of algorithm we come up with, so if we don't use the simple algorithm
  5. like Alice and Bob were using but something more complicated, we would have to show that
  6. nevertheless, this algorithm still runs an exponential running time.
  7. Just by stating that there' s one algorithm for a problem that has exponential running time
  8. does not necessarily mean that the problem itself is hard; it could also mean that we just
  9. haven't felt long enough about designing an appropriate algorithm for that problem.