English 字幕

← 18-29 Evolution Of 3-SAT Algorithms



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

  1. As you can see the randomized algorithms generally have much better time bounds
  2. or well they might not seem much, but you already know that for exponential time algorithms
  3. little differences here so 1.47 versus 1.32 actually makes quite a difference
  4. so they have generally a lot better time bounds than the deterministic algorithms
  5. It seems that randomized algorithms allows us to achieve
  6. a better worst-case running time than deterministic algorithms.
  7. Of course, up here it has the advantage that it's actually done after this amount of time
  8. whereas down here, it's always an expected running time
  9. and as I said you're gambling a little bit.
  10. You cannot be 100% sure that the algorithm
  11. has found a satisfying assignment even though there might be one.