Return to Video

Accepting Certificate - Intro to Algorithms

  • 0:00 - 0:06
    And the answer is p--is indeed contained within np and the reason is if the problem that we had
  • 0:06 - 0:12
    can be decided by some polynomial time algorithm s that takes the input, runs in polynomial time,
  • 0:12 - 0:16
    and either says yes or no correctly for that input, then we can design--
  • 0:16 - 0:20
    remember that the main thing in the definition of np is that it has a verification algorithm,
  • 0:20 - 0:27
    so we can define a verification algorithm like this--define a to take the input and any certificate
  • 0:27 - 0:36
    that simply returns s of x--this runs in polynomial time and it accepts inputs and certificates correctly.
  • 0:36 - 0:42
    So for any input x, there's some certificate that makes it say yes--that is to say any certificate--
  • 0:42 - 0:44
    because if the answer is yes, it's always going to return yes.
  • 0:44 - 0:47
    And if the answer is no, there's no certificate you can give it
  • 0:47 - 0:50
    that would get it to say anything other than no.
  • 0:50 - 0:53
    That's again because it's a growing certificate and actually just giving the answer.
  • 0:53 - 0:57
    So it's satisfies the two things that we need for the problem to be an np.
  • 0:57 - 1:01
    So anything np is also an np.
Title:
Accepting Certificate - Intro to Algorithms
Video Language:
English
Team:
Udacity
Project:
CS215 - Intro to Algorithms
Duration:
01:02

English subtitles

Revisions Compare revisions