Return to Video

06-18 All In P Or NP

  • 0:00 - 0:06
    So our three problems are so closely related that either all of them lie here in NP but not in P
  • 0:06 - 0:08
    or all of them lie in P.
  • 0:08 - 0:11
    We don't know which one it is but it can't be the case that,
  • 0:11 - 0:15
    for example, we have just vertex cover in P and the other two problems here in NP.
  • 0:15 - 0:17
    And how did we show that in the last unit?
  • 0:17 - 0:23
    For clique and independent set, we showed that there was a polynomial time algorithm
  • 0:23 - 0:28
    that could take a graph that was an input to independent set
  • 0:28 - 0:32
    and transform that into a graph that we can use as an input for clique,
  • 0:32 - 0:35
    and once we have solved the clique problem on the transformed graph,
  • 0:35 - 0:39
    that same solution is also the best possible solution to independent set.
  • 0:39 - 0:44
    So we have a polynomial time algorithm, so the algorithm transforms the input of one problem,
  • 0:44 - 0:49
    say X, into an input of another problem, Y.
  • 0:49 - 0:55
    So, for example, we take independent set and transform that graph into an input for clique
  • 0:55 - 0:59
    and now you'll see one of the advantages of working with decision problems
  • 0:59 - 1:04
    because the third condition is rather easy to state because we can now simply say that
  • 1:04 - 1:09
    solving the problem Y on the transformed input yields the same answer
  • 1:09 - 1:12
    as solving the original problem on the original input.
  • 1:12 - 1:16
    So these three statements here are the same thing that you have seen in the last unit.
  • 1:16 - 1:20
    So, we took an input which was a graph to independent set
  • 1:20 - 1:25
    then transformed it into an input for clique and we found out that if we solve clique on that new input,
  • 1:25 - 1:29
    then we would get the same answer that we would've gotten
  • 1:29 - 1:33
    if we had solved independent set directly on the original input.
  • 1:33 - 1:36
    And of course we also saw that the transformation works in the other way,
  • 1:36 - 1:40
    so we could transform an input to clique into an input of independent set
  • 1:40 - 1:43
    and now for a vertex cover and independent set, it was even easier
  • 1:43 - 1:48
    because we didn't even have to transform the input, so basically the transformation was,
  • 1:48 - 1:53
    we could keep the input as it is, the only thing is if we're working with the decision problem,
  • 1:53 - 1:59
    of course, the answer will be a little bit different, so if we have a vertex cover of size k
  • 1:59 - 2:03
    for a graph with N vertices, then for independent set,
  • 2:03 - 2:06
    we must ask if we have an independent set of size n-k.
  • 2:06 -
    But other than that, the transformation here is very easy.
Title:
06-18 All In P Or NP
Team:
Udacity
Project:
CS313 - Theoretical Computer Science
Duration:
02:13
Amara Bot added a translation

English subtitles

Revisions