Return to Video

18-29 Evolution Of 3-SAT Algorithms

  • 0:00 - 0:05
    As you can see the randomized algorithms generally have much better time bounds
  • 0:05 - 0:09
    or well they might not seem much, but you already know that for exponential time algorithms
  • 0:09 - 0:15
    little differences here so 1.47 versus 1.32 actually makes quite a difference
  • 0:15 - 0:20
    so they have generally a lot better time bounds than the deterministic algorithms
  • 0:20 - 0:23
    It seems that randomized algorithms allows us to achieve
  • 0:23 - 0:26
    a better worst-case running time than deterministic algorithms.
  • 0:26 - 0:32
    Of course, up here it has the advantage that it's actually done after this amount of time
  • 0:32 - 0:33
    whereas down here, it's always an expected running time
  • 0:33 - 0:36
    and as I said you're gambling a little bit.
  • 0:36 - 0:38
    You cannot be 100% sure that the algorithm
  • 0:38 -
    has found a satisfying assignment even though there might be one.
タイトル:
18-29 Evolution Of 3-SAT Algorithms
Team:
Udacity
プロジェクト:
CS313 - Theoretical Computer Science
Duration:
0:42
Amara Bot added a translation

English subtitles

改訂