Return to Video

22x-01 The Truth About P And NP

  • 0:00 - 0:02
    All right. Welcome to the final exam.
  • 0:02 - 0:07
    Let's go ahead and start off with some questions about P vs NP.
  • 0:07 - 0:12
    So, I'd like you to check the boxes here for the statements that you think are true.
  • 0:12 - 0:19
    First, if any problem in NP is polynomial-time solvable, then P = NP.
  • 0:19 - 0:24
    The second question is if any problem in NP provably requires
  • 0:24 - 0:28
    exponential time to solve, then P ≠ NP.
  • 0:28 - 0:34
    And finally, if P ≠ NP, then some problems solvable in polynomial time
  • 0:34 - 0:39
    on a nondeterministic RAM will require exponential time to solve on a deterministic RAM.
  • 0:39 -
    So, please check all that are true.
タイトル:
22x-01 The Truth About P And NP
Team:
Udacity
プロジェクト:
CS313 - Theoretical Computer Science
Duration:
0:42
Amara Bot added a translation

English subtitles

改訂