PK T#iAYa9 9 = Unit_2.2_-_Non-deterministic_RAM/01-Gathering_Evidence.en.srt1
00:00:00,000 --> 00:00:05,010
So since finding a mathematical proof for showing the intractability of the problems that
2
00:00:05,010 --> 00:00:09,580
Alice, Bob, and Carol are working on seems to be rather hard,
3
00:00:09,580 --> 00:00:14,970
we're first going to start with gathering evidence that their problems might be intractable.
4
00:00:14,970 --> 00:00:18,490
Of course, we don't yet really know if their problems really are intractable
5
00:00:18,490 --> 00:00:22,760
because as we have just seen there are also arguments why their problems
6
00:00:22,760 --> 00:00:27,330
could actually be tractable because just having an exponential number of solutions
7
00:00:27,330 --> 00:00:31,550
does not necessarily mean that their problems are difficult but we're going to see how it turns out.
8
00:00:31,550 --> 00:00:37,320
So how can we gather evidence that the problems of Alice, Bob, and Carol could be intractable?
9
00:00:37,320 --> 00:00:43,000
One way could be what we have done in the last unit and that is if you recall in the last unit
10
00:00:43,000 --> 00:00:47,790
we showed that all of these three problems are either tractable or intractable.
11
00:00:47,790 --> 00:00:53,560
So one way to gather evidence that they are intractable is to find more and more problems
12
00:00:53,560 --> 00:00:56,940
for which we also don't know polynomial time algorithms
13
00:00:56,940 --> 00:00:59,610
and connect them to the problems that we know.
14
00:00:59,610 --> 00:01:06,100
So if we had this huge network of problems but we say if we find a polynomial time algorithm
15
00:01:06,100 --> 00:01:09,110
for just one of them, all of them would be solvable in polynomial time
16
00:01:09,110 --> 00:01:15,490
but nobody has yet found such an algorithm that would already be rather strong evidence that
17
00:01:15,490 --> 00:01:18,890
also clique, vertex cover, and independent set might be hard.
18
00:01:18,890 --> 00:01:23,480
So we might, for example, end up with thousands of highly relevant problems
19
00:01:23,480 --> 00:01:27,280
for which no one has so far found a polynomial time algorithm
20
00:01:27,280 --> 00:01:31,340
and if they're all connected that would be not a mathematical proof but it would be
21
00:01:31,340 --> 00:01:35,390
a somewhat convincing body of evidence for these problems' hardness.
22
00:01:35,390 --> 00:01:39,620
And in fact, I will introduce you to such a collection of problems at the end of this unit
23
00:01:39,620 --> 00:01:41,810
and we'll also have a closer look in the next units.
24
00:01:41,810 --> 00:01:45,540
But today actually, we're going to do something that is a little bolder.
25
00:01:45,540 --> 00:01:51,420
We're still not going to be able to achieve a mathematical proof of intractability
26
00:01:51,420 --> 00:01:54,720
but we're going to do something that I would say is somewhere in between
27
00:01:54,720 --> 00:01:57,320
gathering evidence and a mathematic proof.
28
00:01:57,320 --> 00:02:00,420
And the way we're going to do this is as follows.
29
00:02:00,420 --> 00:02:05,600
I'm going to introduce to you a type of computer that is extremely powerful.
30
00:02:05,600 --> 00:02:11,540
So powerful in fact that no one has ever conceived if it could actually be built.
31
00:02:11,540 --> 00:02:17,970
And then what I'll show you is that if there was a polynomial time algorithm for vertex cover
32
00:02:17,970 --> 00:02:25,190
or clique or independent set, that would be like having a blueprint for this super powerful computer.
33
00:02:25,190 --> 00:02:29,470
We won't be able to show that it's imposible to build such a computer,
34
00:02:29,470 --> 00:02:36,790
but it is pretty good evidence that those three problems up here are very tough problems to solve.
35
00:02:36,790 --> 00:02:40,450
So what makes this computer that I'm about to introduce to you so powerful?
36
00:02:40,450 --> 00:02:46,160
Well, roughly speaking, it's so powerful because it has the capability to guess things for us
37
00:02:46,160 --> 00:02:50,100
and it will guess them correctly but you're going to see in a minute what I mean by that.
38
00:02:50,100 --> 00:02:56,060
First of all, let's have a look once more at the three problems: click, vertex cover, and independent set.
39
00:02:56,060 --> 00:03:00,010
And have a look at how a machine that would be capable of guessing things for us
40
00:03:00,010 --> 00:03:04,060
could potentially make the solution to these problems very easy.
41
00:03:04,060 --> 00:03:07,930
And we're going to do this as a quiz and what I would like you to think about is
42
00:03:07,930 --> 00:03:11,300
what the three problems we have been talking about so far have in common.
43
00:03:11,300 --> 00:03:14,480
And I'm going to give you a number of choices and I would like you to tell me
44
00:03:14,480 --> 00:03:17,300
which ones of these you think are true and there can be more than one.
45
00:03:17,300 --> 00:03:20,650
So there's four possible choices here and again more than one of these can be true.
46
00:03:20,650 --> 00:03:24,440
So what do all of these three problems up here have in common?
47
00:03:24,440 --> 00:03:28,520
Choice #1, we have not found a polynomial time algorithm for them yet.
48
00:03:28,520 --> 00:03:31,000
Choice #2, they are not practically relevant.
49
00:03:31,000 --> 00:03:34,210
Choice #3, the simple algorithms that we have found so far
50
00:03:34,210 --> 00:03:36,770
go through an exponential number of solutions.
51
00:03:36,770 --> 00:03:42,880
And finally, for the simple algorithms, for any given 0 and 1 assignment to the vertices
52
00:03:42,880 --> 00:03:48,310
so we have already assigned the values of 0 and 1 to them, it is relatively easy to figure out
53
00:03:48,310 --> 00:03:50,840
if that assignment is a valid solution.
54
00:03:50,840 --> 99:59:59,000
And if it is a valid solution, how large that solution is? So please check all of these that are correct.
PK U#iAY̦b F Unit_2.2_-_Non-deterministic_RAM/02-Gathering_Evidence_Solution.en.srt1
00:00:00,000 --> 00:00:02,170
So the first one is obviously correct.
2
00:00:02,170 --> 00:00:05,800
So far, we have not found a polynomial time algorithm for the three problems here.
3
00:00:05,800 --> 00:00:09,930
We've shown in the last unit that they are practically relevant or at least
4
00:00:09,930 --> 00:00:13,680
slightly simplified versions of highly relevant problems.
5
00:00:13,680 --> 00:00:16,460
All of the simple problems go through an exponential number of solutions.
6
00:00:16,460 --> 00:00:20,870
That's what made all of those simple algorithm so bad and their running time--
7
00:00:20,870 --> 00:00:25,130
all led to the exponential running time, but the thing is going through that exponential
8
00:00:25,130 --> 00:00:28,910
number of 0-1 assignments is also what made those problems hard to solve.
9
00:00:28,910 --> 00:00:34,360
If you have given a certain assignment, checking if that is valid and how large it is--
10
00:00:34,360 --> 00:00:38,780
for example, if it's better than a solution you have found so far--that is relatively easy.
11
00:00:38,780 --> 00:00:40,680
It's doable in polynomial time.
12
00:00:40,680 --> 00:00:44,600
Now, the answers to this quiz might seem rather obvious to you
13
00:00:44,600 --> 00:00:47,220
and you might be wondering what we're going to do with those answers,
14
00:00:47,220 --> 99:59:59,000
but I promise you it will all make sense very soon.
PK V#iA$i 4 Unit_2.2_-_Non-deterministic_RAM/03-if-better.en.srt1
00:00:00,000 --> 00:00:04,370
So in the last unit, we talked about the simple algorithms
2
00:00:04,370 --> 00:00:09,190
for our three problems that have to go through an exponential number of solutions
3
00:00:09,190 --> 00:00:13,900
to try all possible assignments of 0 and 1 to the vertices.
4
00:00:13,900 --> 00:00:21,260
And now I haven't told you yet what this super powerful computer down here in the left corner
5
00:00:21,260 --> 00:00:25,840
is actually capable of and the ability that this computer here has
6
00:00:25,840 --> 00:00:32,820
is that it can help us figure out the best possible 0 and 1 assignment to the vertices
7
00:00:32,820 --> 00:00:35,250
without actually going through them.
8
00:00:35,250 --> 00:00:41,470
And the way this computer can help us is that it has a special instruction that a normal computer
9
00:00:41,470 --> 00:00:46,990
or even the RAM model does not have and that instruction is called if-better.
10
00:00:46,990 --> 00:00:50,040
And I'm going to explain to you in a second what that means.
11
00:00:50,040 --> 00:00:55,170
So the if-better function basically works like a normal if-else instruction on the RAM.
12
00:00:55,170 --> 00:01:01,580
So the normal if-else instruction is if this part here which I haven't specified yet is true
13
00:01:01,580 --> 00:01:07,950
then this part of the code not yet written is executed and otherwise this part down here is executed.
14
00:01:07,950 --> 00:01:13,780
The second property is that calling the if-better function will cost us polynomial time.
15
00:01:13,780 --> 00:01:19,280
So a normal if-else on the RAM just costs one time step or constant time
16
00:01:19,280 --> 00:01:22,420
and calling this function here will cost polynomial time.
17
00:01:22,420 --> 00:01:24,620
And now here comes the special property of this function.
18
00:01:24,620 --> 00:01:29,250
Normally when you have an if, you would have to specify some condition here so that
19
00:01:29,250 --> 00:01:32,910
if the condition is satisfied this part of the code is executed.
20
00:01:32,910 --> 00:01:36,300
And if it's not satisfied, then this part here is executed.
21
00:01:36,300 --> 00:01:42,740
Now the if-better is a function that will figure out by itself if it's better for us,
22
00:01:42,740 --> 00:01:45,140
and I'm going to show you in a minute what I mean by that,
23
00:01:45,140 --> 00:01:50,290
if it's better for us to execute this part up here or this part down here.
24
00:01:50,290 --> 00:01:55,270
It will always, if you will, guess correctly which part of the code to execute.
25
00:01:55,270 --> 00:01:57,940
Now, the first time you hear this, it takes a bit getting used to.
26
00:01:57,940 --> 00:02:02,190
So let me give you one example for our vertex cover how we could use this powerful function
27
00:02:02,190 --> 99:59:59,000
to solve vertex cover almost trivially.
PK V#iAi8tD D F Unit_2.2_-_Non-deterministic_RAM/04-Vertex_Cover_With_if-better.en.srt1
00:00:00,000 --> 00:00:02,930
So we're working with the decision version of vertex cover here.
2
00:00:02,930 --> 00:00:09,450
So as an input, we're giving a graph G with n vertices and an integer k.
3
00:00:09,450 --> 00:00:17,010
And the output is "yes" if G has a vertex cover of size at most k and "no" otherwise.
4
00:00:17,010 --> 00:00:21,030
So the first time you see this kind of use of the if-better function
5
00:00:21,030 --> 00:00:25,490
it might still seem a bit strange to you so I'm going to explain to you what it does
6
00:00:25,490 --> 00:00:26,890
and how we're using it here.
7
00:00:26,890 --> 00:00:33,970
We're using this if-better function to guess for us which vertices to put into the vertex cover
8
00:00:33,970 --> 00:00:36,800
and which vertices we can leave out.
9
00:00:36,800 --> 00:00:41,170
Then we check if the assignment is valid although actually we wouldn't have to do that
10
00:00:41,170 --> 00:00:46,420
but I'll get into that in a minute and if the size of the assignment that we have found is at most k
11
00:00:46,420 --> 00:00:52,940
we say "yes, the graph has a vertex cover of size at most k and no otherwise."
12
00:00:52,940 --> 00:00:58,510
So as you can see, we're putting a lot of trust into this part here of the function
13
00:00:58,510 --> 00:01:06,680
because we're basically trusting the if-better to tell us correctly whether we should
14
00:01:06,680 --> 00:01:10,130
put a vertex into the vertex cover or whether we shouldn't do that.
15
00:01:10,130 --> 00:01:13,830
And that is why I basically said that the computer that has this function available
16
00:01:13,830 --> 00:01:19,730
is extremely powerful because if you can trust the if-better to do exactly what we want for us
17
00:01:19,730 --> 00:01:24,590
which is guess the best possible assignment then of course this significantly changes
18
00:01:24,590 --> 00:01:26,490
the running time of the algorithm here.
19
00:01:26,490 --> 00:01:31,450
So let's do a little quiz--what is the running time of this algorithm here for a graph with n vertices
20
00:01:31,450 --> 00:01:36,480
if we can trust the if-better function to perform as specified and guess the best possible assignment
21
00:01:36,480 --> 99:59:59,000
of 0s and 1s to the vertices.
PK W#iA_j j F Unit_2.2_-_Non-deterministic_RAM/05-Vertex_Cover_With_if-better.en.srt1
00:00:00,000 --> 00:00:04,810
And the solution here is if we have the ifbetter function available, then we can solve
2
00:00:04,810 --> 00:00:10,920
vertex cover in polynomial time because as we said the ifbetter function works in polynomial time
3
00:00:10,920 --> 00:00:13,740
and we're calling it once for each vertex in the graph.
4
00:00:13,740 --> 00:00:18,860
So we're calling it n times it works in polynomial time so this part here of finding the
5
00:00:18,860 --> 00:00:22,890
best possible assignment of theirs and once to the vertices that works in polynomial time.
6
00:00:22,890 --> 00:00:26,800
And as you know from before, checking if an assignment is valid and checking the size
7
00:00:26,800 --> 00:00:29,440
of an assignment that's also doable in polynomial time.
8
00:00:29,440 --> 00:00:34,480
So the total running time of the algorithm is polynomial in n the number of vertices,
9
00:00:34,480 --> 00:00:38,910
and the right thing is that, although you shouldn't probably anthropomorphise this,
10
00:00:38,910 --> 00:00:42,740
the ifbetter function always knows what will help us.
11
00:00:42,740 --> 00:00:49,090
So if we were trying to solve clique or independent set instead of vertex cover,
12
00:00:49,090 --> 00:00:54,360
the ifbetter function would somehow know this and give us a different assignment
13
00:00:54,360 --> 00:00:58,610
of 0s and 1s to the vertices, which would however still be guaranteed to be optimal,
14
00:00:58,610 --> 99:59:59,000
and that is what make this function so extremely powerful.
PK X#iA8B:
:
= Unit_2.2_-_Non-deterministic_RAM/06-Complexity_Classes.en.srt1
00:00:00,000 --> 00:00:03,850
So now with that kind of magic function if-better we could solve all the three problems
2
00:00:03,850 --> 00:00:05,920
we have looked at so far in polynomial time.
3
00:00:05,920 --> 00:00:08,840
We could solve vertex cover, we could solve independent set,
4
00:00:08,840 --> 00:00:10,740
and we could solve clique in polynomial time.
5
00:00:10,740 --> 00:00:15,830
Now theoretical computer scientists like to divide problems into so-called complexity classes.
6
00:00:15,830 --> 00:00:20,890
And a complexity class basically contains all problems that can be solved
7
00:00:20,890 --> 00:00:25,140
on a given machine within a specified time or a specified memory or even both.
8
00:00:25,140 --> 00:00:27,200
But we're going to stick with time for now.
9
00:00:27,200 --> 00:00:31,650
So if we draw this as a matrix and put time here and the machine here
10
00:00:31,650 --> 00:00:34,680
then so far we learned about two different types of time.
11
00:00:34,680 --> 00:00:38,400
We have learned about polynomial time and we have learned about exponential time,
12
00:00:38,400 --> 00:00:44,280
and we have the normal RAM, the model that has basically the same capabilities as any computer
13
00:00:44,280 --> 00:00:49,540
that you know, and we have just learned about the RAM that has the if-better function available.
14
00:00:49,540 --> 00:00:52,650
Each of these fields here in the matrix is a complexity class.
15
00:00:52,650 --> 00:00:59,370
So this field here, for example, would contain all problems that can be solved
16
00:00:59,370 --> 00:01:03,300
in exponential time on a normal RAM.
17
00:01:03,300 --> 00:01:11,110
So vertex cover, independent set, and clique would all be contained in this class.
18
00:01:11,110 --> 00:01:15,320
But of course they can also be contained in other classes and I would actually like you
19
00:01:15,320 --> 00:01:18,300
to figure this out as our next quiz and the question is,
20
00:01:18,300 --> 00:01:22,630
in which other complexity classes, so this one here, this one here, or this one here,
21
00:01:22,630 --> 00:01:25,870
can we put our three problems vertex cover, independent set, and clique?
22
00:01:25,870 --> 00:01:28,900
And I would like you to make a check mark if you're sure
23
00:01:28,900 --> 00:01:31,840
that we can put these problems into that complexity class.
24
00:01:31,840 --> 99:59:59,000
If you're sure that we cannot do that or if we're not certain, I want you to leave that field blank.
PK Y#iA) F Unit_2.2_-_Non-deterministic_RAM/07-Complexity_Classes_Solution.en.srt1
00:00:00,000 --> 00:00:03,540
And the answer here is as follows--so first of all, it's important to notice that
2
00:00:03,540 --> 00:00:09,660
a RAM that has the if-better function available is at least as powerful as a normal RAM
3
00:00:09,660 --> 00:00:12,440
because all we're adding is this additional instruction
4
00:00:12,440 --> 00:00:15,200
but we can still do anything that we could do before.
5
00:00:15,200 --> 00:00:17,810
So this here is clearly a check mark.
6
00:00:17,810 --> 00:00:21,660
Vertex cover, independent set, and clique would be solvable in exponential time.
7
00:00:21,660 --> 00:00:24,330
Also, if we have this if-better function available.
8
00:00:24,330 --> 00:00:29,910
And the second thing is that in the well sort of programming example that we just had
9
00:00:29,910 --> 00:00:34,670
we also saw that the if-better function is so powerful that it will allow us to solve
10
00:00:34,670 --> 00:00:38,300
vertex cover, independent set, and clique in polynomial time
11
00:00:38,300 --> 00:00:40,660
if we have the if-better function available.
12
00:00:40,660 --> 00:00:43,820
And of course this one down here, that unfortunately has to stay blank
13
00:00:43,820 --> 00:00:49,000
but not because we're sure that these problems, vertex cover, independent set, and clique
14
00:00:49,000 --> 00:00:53,790
don't have a polynomial time algorithm but simply because we don't really know yet.
15
00:00:53,790 --> 00:00:56,310
We will come back to this matrix picture here in a minute.
16
00:00:56,310 --> 99:59:59,000
But let's turn our attention back to the RAM machine for a moment now.
PK Z#iA ?l l ; Unit_2.2_-_Non-deterministic_RAM/08-Two_Types_Of_RAM.en.srt1
00:00:00,000 --> 00:00:02,390
So, by now, we know two types of RAM machine.
2
00:00:02,390 --> 00:00:06,399
The first one here on the left is the one that we introduced in the first unit
3
00:00:06,399 --> 00:00:09,449
and it does not allow to use the if-better function.
4
00:00:09,449 --> 00:00:12,950
So, this is something that is although as we discussed
5
00:00:12,950 --> 00:00:14,720
it has some differences to your standard computer.
6
00:00:14,720 --> 00:00:17,780
It is more or less close to your normal computer.
7
00:00:17,780 --> 00:00:21,820
And here on the right side, we have the RAM with the if-better function
8
00:00:21,820 --> 00:00:24,269
and this of course is a much more powerful machine
9
00:00:24,269 --> 00:00:26,420
so as you can see it is buzzing with computational power here
10
00:00:26,420 --> 00:00:33,520
and this is totally unlike your standard computer because it has this guessing function about n
11
00:00:33,520 --> 00:00:37,100
and of course, if somebody asked us to build this sort of RAM machine
12
00:00:37,100 --> 00:00:41,680
at least I would turn them down immediately because it's not clear at all
13
00:00:41,680 --> 00:00:43,740
how we should write such a function.
14
00:00:43,740 --> 00:00:49,210
It seems far too powerful and at least to me frankly also a bit mysterious.
15
00:00:49,210 --> 00:00:52,840
So, that's also basically the difference between the two machines
16
00:00:52,840 --> 00:00:59,620
because here on the standard RAM, it's very clear what each of the functions that it has does.
17
00:00:59,620 --> 00:01:04,330
Actually, if you know what the machine is currently doing then you can always predict
18
00:01:04,330 --> 00:01:08,569
what it will do next because for every instruction it's very clear what it does
19
00:01:08,569 --> 00:01:13,700
given certain variables or inputs and not so with the RAM that uses if-better function above.
20
00:01:13,700 --> 00:01:18,890
Actually, most of the time unless this function is use, it's still clear what happens next
21
00:01:18,890 --> 00:01:23,330
but every time this function here is called, we don't really know what's going to happen next.
22
00:01:23,330 --> 00:01:26,610
It seems as if only this function here kind of knows.
23
00:01:26,610 --> 00:01:31,920
Or if you put it in another way, if you go through an algorithm that is written on a standard RAM
24
00:01:31,920 --> 00:01:36,070
then you can basically go through it step by step by step by hand
25
00:01:36,070 --> 00:01:39,180
and say how its going to behave.
26
00:01:39,180 --> 00:01:42,830
For this RAM over here, you could also go through it step, by step, by step
27
00:01:42,830 --> 00:01:47,979
but once you encounter this if-better function here, you could not really say what its going to do next.
28
00:01:47,979 --> 00:01:52,330
You would have to try different cases and so in order to better distinguish those two models,
29
00:01:52,330 --> 00:01:55,630
there is a special terminology in theoretical computer science
30
00:01:55,630 --> 00:01:58,800
called determinism and non-determinism.
31
00:01:58,800 --> 00:02:03,280
And this standard RAM machine because we always know what's going to happen next
32
00:02:03,280 --> 00:02:09,448
is called deterministic and surprise this one over here is called non-deterministic.
33
00:02:09,448 --> 00:02:13,230
Now, it's very important that you familiarize yourself with those two terms
34
00:02:13,230 --> 00:02:16,980
because we're going to use them a lot in this course,
35
00:02:16,980 --> 00:02:20,770
and just to make you think about them a little bit more, I would like to do a little quiz with you.
36
00:02:20,770 --> 00:02:22,060
So, what I would like you to think about is,
37
00:02:22,060 --> 00:02:28,820
if you're using the if-better function in a program and we run the same program code multiple times,
38
00:02:28,820 --> 00:02:32,710
can we get different solutions if we're running it on the same input
39
00:02:32,710 --> 00:02:34,680
or will we always get the same solution?
40
00:02:34,680 --> 00:02:40,140
So if you think that non-determinism can produce different solutions on the same input
41
00:02:40,140 --> 99:59:59,000
using the same code then please check yes, otherwise, check no.
PK [#iAs! ! ; Unit_2.2_-_Non-deterministic_RAM/09-Two_Types_Of_RAM.en.srt1
00:00:00,000 --> 00:00:04,840
And the answer here is no. So a non-deterministic RAM.
2
00:00:04,840 --> 00:00:10,090
If it's running the same cod on the same input, it will always return the same solution
3
00:00:10,090 --> 00:00:14,110
because this if better function here, although we don't know what it's going to do.
4
00:00:14,110 --> 00:00:17,740
It still behaves in a consistent way and this is actually quite important
5
00:00:17,740 --> 99:59:59,000
because non-determinism is not the same thing as randomness.
PK [#iAZ) ) K Unit_2.2_-_Non-deterministic_RAM/10-Building_A_Non-Deterministic_Ram.en.srt1
00:00:00,000 --> 00:00:03,560
As you have seen, non-determinism is pretty powerful,
2
00:00:03,560 --> 00:00:09,780
so the question is, of course, could we actually build a non-deterministic RAM?
3
00:00:09,780 --> 00:00:12,970
And as I told you before, I have no idea how you would do that,
4
00:00:12,970 --> 00:00:16,850
so if somebody ask me to build a non-deterministic RAM, I would turn them down
5
00:00:16,850 --> 00:00:21,250
although if you could build one of these, you would certainly become quite rich and famous.
6
00:00:21,250 --> 00:00:27,830
The next best thing we can do to building a non-deterministic RAM though is simulating one.
7
00:00:27,830 --> 00:00:32,170
And of course you will be asking yourself, well, if he doesn't know
8
00:00:32,170 --> 00:00:36,750
how to build a non-deterministic RAM, how is he going to simulate one?
9
00:00:36,750 --> 00:00:43,190
Well, the answer is actually not that difficult but I'll have to warn you because the simulation
10
00:00:43,190 --> 00:00:48,300
will not be very satisfying or at least will have to pay quite a steep price for the simulation.
11
00:00:48,300 --> 00:00:52,830
So the first thing we should probably talk about when we want to simulate
12
00:00:52,830 --> 00:00:56,480
a non-deterministic RAM on a deterministic RAM is
13
00:00:56,480 --> 00:01:01,980
how would we simulate a deterministic RAM on a deterministic RAM?
14
00:01:01,980 --> 00:01:05,610
So basically, a picture like this, you have a deterministic RAM and of course,
15
00:01:05,610 --> 00:01:08,710
it's branded as a deterministic RAM and on that machine,
16
00:01:08,710 --> 00:01:14,130
you do a simulation of another deterministic RAM and this might look
17
00:01:14,130 --> 00:01:16,410
a little bit more complicated than it actually is.
18
00:01:16,410 --> 00:01:22,060
So, all it means is that if you have a program code that you run on a deterministic RAM,
19
00:01:22,060 --> 00:01:27,280
instead of running this code directly, you have another program
20
00:01:27,280 --> 00:01:32,460
and this program is basically going through your code and simulating what your code is doing.
21
00:01:32,460 --> 00:01:35,420
And this program here which would be the simulator
22
00:01:35,420 --> 00:01:42,270
is basically looking at the code and simulating what this code would actually do.
23
00:01:42,270 --> 00:01:47,750
Without running it directly on the machine, so it's running indirectly on this machine here.
24
00:01:47,750 --> 00:01:50,610
Another way you can look at the simulation is this diagram here,
25
00:01:50,610 --> 00:01:53,450
so you start out with a certain program that you want to simulate
26
00:01:53,450 --> 00:01:57,760
and of course you also start out not only with the program but also with a memory of that RAM
27
00:01:57,760 --> 00:02:02,410
and if you remember in the last unit, we said that the RAM had actually different kinds of memory,
28
00:02:02,410 --> 00:02:05,610
some memory for the input, some for the output, and so on
29
00:02:05,610 --> 00:02:08,039
but we'll just draw this as a single memory here.
30
00:02:08,039 --> 00:02:13,700
So, we start out at the first line of code and then because it's a deterministic RAM,
31
00:02:13,700 --> 00:02:16,870
that line of code specifies exactly what's going to happen next,
32
00:02:16,870 --> 00:02:19,980
so it specifies certain modifications that we make to the memory,
33
00:02:19,980 --> 00:02:24,830
so we might change this variable here or even change two variables
34
00:02:24,830 --> 00:02:28,000
although this is not often going to happen in one single line of code,
35
00:02:28,000 --> 00:02:31,890
but we make some modifications to the memory and we're still in the first line of code here,
36
00:02:31,890 --> 00:02:36,460
then, we're going to check if that line here actually is a statement that tells us that we are done.
37
00:02:36,460 --> 00:02:41,950
If that is the case, then the simulation would also be done, but let's say that this is not the case.
38
00:02:41,950 --> 00:02:44,690
We can then go to the next line of code in our simulation
39
00:02:44,690 --> 00:02:48,810
and again that line will also specify some other things that we are to do,
40
00:02:48,810 --> 00:02:53,240
so most of the time it's going to be again changing variables, maybe it's reading the variable,
41
00:02:53,240 --> 00:02:59,220
but let's say it's also changing additional variables, so we check again if we're done,
42
00:02:59,220 --> 00:03:02,070
we go to the next line of code and so on, until we're done.
43
00:03:02,070 --> 00:03:07,690
And the reason why this simulation works and it actually works rather efficiently I would say,
44
00:03:07,690 --> 00:03:13,960
is a determinism means that each line of code specifies exactly what's going to happen next.
45
00:03:13,960 --> 00:03:16,530
Now for our next quiz, I would like you to think a little bit
46
00:03:16,530 --> 00:03:21,800
about the cost of this simulation or the properties of this simulation,
47
00:03:21,800 --> 00:03:26,530
so I would like you to tell me if instead of executing a program directly
48
00:03:26,530 --> 00:03:30,400
or running it directly on a machine, we do a simulation of that code.
49
00:03:30,400 --> 00:03:32,520
What are the properties of that simulation?
50
00:03:32,520 --> 00:03:36,430
In other words, what does it caused us to do such a simulation?
51
00:03:36,430 --> 00:03:39,220
Obviously, it will take longer because we are wrapping
52
00:03:39,220 --> 00:03:43,790
some other code around the original program, but how much longer does it take?
53
00:03:43,790 --> 00:03:47,910
Does it take longer by a polynomial time factor and by a polynomial time factor,
54
00:03:47,910 --> 00:03:53,030
I mean, if for example, the original algorithm would run in O(n²) time,
55
00:03:53,030 --> 00:03:58,340
or O(n⁴) time, something like that.
56
00:03:58,340 --> 00:04:04,740
Does it take longer exponentially, maybe, so if the original run in O(n²) time,
57
00:04:04,740 --> 00:04:11,430
we would now run and say (2^n) time or (2^n) times and square time,
58
00:04:11,430 --> 00:04:17,060
and finally, if this sort of simulation robust, so will it always give us the same result
59
00:04:17,060 --> 00:04:19,070
that the original program would have given us,
60
00:04:19,070 --> 99:59:59,000
or is there a possibility that such a simulation can make a mistake?
PK \#iAUHJ K Unit_2.2_-_Non-deterministic_RAM/11-Building_A_Non-Deterministic_Ram.en.srt1
00:00:00,000 --> 00:00:01,630
And there are two correct answers here.
2
00:00:01,630 --> 00:00:05,950
The first one is the simulation takes longer by a polynomial time factor.
3
00:00:05,950 --> 00:00:08,920
Now, it's a bit difficult if you wanted to specify exactly
4
00:00:08,920 --> 00:00:11,790
how much longer a simulation like this takes.
5
00:00:11,790 --> 00:00:17,120
In my point of view, you would not even take polynomially longer but only a constant factor,
6
00:00:17,120 --> 00:00:19,990
but polynomial is safe enough because in this course we're mostly
7
00:00:19,990 --> 00:00:23,670
differentiating between polynomial and exponential running time.
8
00:00:23,670 --> 00:00:28,140
Now, the reason why it only takes polynomial time longer is that, as I said before,
9
00:00:28,140 --> 00:00:34,040
once we're in the certain line of code, this line of code specifies exactly what is going to happen next.
10
00:00:34,040 --> 00:00:40,060
So it's mostly an overhead of simulating what this line here of code does, but as we said
11
00:00:40,060 --> 00:00:44,960
when we specify the RAM model, each line here is a simple operations, so it takes constant
12
00:00:44,960 --> 00:00:46,670
amount of time on the RAM.
13
00:00:46,670 --> 00:00:52,410
I think it's fair to say that it will only take polynomially more time if you simulate what it does.
14
00:00:52,410 --> 00:00:56,240
It doesn't do anything really complex. So the second answer here is wrong.
15
00:00:56,240 --> 00:01:01,740
The simulation is also always correct because there's no involvement of randomness
16
00:01:01,740 --> 00:01:03,420
or guessing and such.
17
00:01:03,420 --> 00:01:06,470
So if the simulator is programmed correctly, we will always get
18
00:01:06,470 --> 00:01:08,830
the same result that we would have originally gotten.
19
00:01:08,830 --> 99:59:59,000
It only takes longer time.
PK ]#iAg M Unit_2.2_-_Non-deterministic_RAM/12-Simulating_A_Non-Deterministic_Ram.en.srt1
00:00:00,000 --> 00:00:06,380
So, how can we now simulate a non-deterministic RAM on a RAM?
2
00:00:06,380 --> 00:00:12,360
Because that is what we originally set out to do and it turns out, it's actually not that difficult
3
00:00:12,360 --> 00:00:15,450
once we have our deterministic RAM simulator
4
00:00:15,450 --> 00:00:18,780
because what happens if you're in a given line or code?
5
00:00:18,780 --> 00:00:23,700
There's two different things that can happen, one it's a normal instruction such as
6
00:00:23,700 --> 00:00:27,210
one you would find on a deterministic RAM and in this case,
7
00:00:27,210 --> 00:00:31,870
the simulator can just go on running the same way that it would have gone for the deterministic RAM.
8
00:00:31,870 --> 00:00:38,350
The only difference is if the simulator encounters this, if better, here then it has a problem
9
00:00:38,350 --> 00:00:42,840
because then simulating what this line of code does is not straight forward anymore.
10
00:00:42,840 --> 00:00:47,730
The if better might execute the first part of the code or the second part of the code
11
00:00:47,730 --> 00:00:52,990
around which it has written, so we have to work a little bit on this part here of the simulation.
12
00:00:52,990 --> 00:00:54,660
So, we have to distinguish two cases.
13
00:00:54,660 --> 00:00:59,950
One is if we have a normal instruction, then we'll just do a simulation,
14
00:00:59,950 --> 00:01:04,040
but if we have an if better, then we don't know how the machine continues
15
00:01:04,040 --> 00:01:09,670
so what our simulator would then do, is it will branch into two different possibilities.
16
00:01:09,670 --> 00:01:12,870
So it will start two new simulations.
17
00:01:12,870 --> 00:01:19,590
In one simulation, it will continue assuming the if better function executes the first part of the code,
18
00:01:19,590 --> 00:01:22,550
so the one that came directly after the if better.
19
00:01:22,550 --> 00:01:26,880
And then the other case, it will continue assuming that the if better function
20
00:01:26,880 --> 00:01:31,800
executes the second part of the code, so the part that comes after the else statement.
21
00:01:31,800 --> 00:01:36,320
And of course, once you have this branching, you don't have one single simulation anymore,
22
00:01:36,320 --> 00:01:38,690
but you have to continue with two simulations.
23
00:01:38,690 --> 00:01:43,850
One simulation makes this assumption here, the other one makes this assumption down here.
24
00:01:43,850 --> 00:01:50,010
And if you now encounter the if better statement, then again,
25
00:01:50,010 --> 00:01:54,420
you will have to branch into two possibilities up here and the same thing down here.
26
00:01:54,420 --> 00:01:58,290
If you continue the simulation with the assumption what happened the first time
27
00:01:58,290 --> 00:02:01,670
you encountered the if better function, and now you go on, then again,
28
00:02:01,670 --> 00:02:07,010
if you find, if better, again you will have to split into two different possibilities.
29
00:02:07,010 --> 00:02:11,980
And of course, running a simulation this way where you have to split into two possibilities
30
00:02:11,980 --> 00:02:15,820
all the time comes at a price which I'm sure you can figure out by now.
31
00:02:15,820 --> 00:02:20,790
And my question to you is, if we have a program that uses the if better function,
32
00:02:20,790 --> 00:02:26,790
and times, how many simulations or how many different simulations do we end up running?
33
00:02:26,790 --> 99:59:59,000
Is it n simulations, is it n² simulations, is it 2^n simulations, or something else?
PK ]#iA6P7 M Unit_2.2_-_Non-deterministic_RAM/13-Simulating_A_Non-Deterministic_Ram.en.srt1
00:00:00,000 --> 00:00:04,430
And the answer here is that we end up with 2^n simulations,
2
00:00:04,430 --> 00:00:09,660
because each time that we encounter if-better we have to split into two possibilities
3
00:00:09,660 --> 00:00:14,680
and then the next time, we encounter if-better we have to split each one of those two possibilities
4
00:00:14,680 --> 00:00:20,060
into two possibilities each and so we end up with an exponential growth.
5
00:00:20,060 --> 00:00:24,200
And that is why I told you in the beginning that simulating a non-deterministic RAM
6
00:00:24,200 --> 00:00:29,970
on a deterministic RAM is possible, but it's a very unsatisfying simulation
7
00:00:29,970 --> 00:00:35,630
because we pay for it with exponential time and what that means is, for example, for vertex cover,
8
00:00:35,630 --> 00:00:41,580
yes, we can solve vertex cover on a non-deterministic RAM in polynomial time.
9
00:00:41,580 --> 00:00:45,230
But if we do the stimulation of that non-deterministic code,
10
00:00:45,230 --> 00:00:47,220
we end up with exponential time again.
11
00:00:47,220 --> 00:00:53,110
Now of course the question would be, could you simulate a non-deterministic RAM more efficiently?
12
00:00:53,110 --> 00:00:56,440
For example, only using a polynomial number of simulations.
13
00:00:56,440 --> 00:00:59,100
So, in a way we're back where we started.
14
00:00:59,100 --> 00:01:02,840
We found out that we can not simulate a non-deterministic RAM,
15
00:01:02,840 --> 00:01:05,170
but that's going to take us exponential time.
16
00:01:05,170 --> 00:01:08,520
So the question remains, is there a better way to simulate non-determinism
17
00:01:08,520 --> 00:01:13,410
ideally with polynomial time or does simulating non-determinism
18
00:01:13,410 --> 99:59:59,000
on a deterministic RAM always lead to exponential time?
PK `#iA5_V : Unit_2.2_-_Non-deterministic_RAM/14-Polynomial_Time.en.srt1
00:00:00,000 --> 00:00:02,940
So remember the 2 by 2 matrix that we drew a while ago.
2
00:00:02,940 --> 00:00:06,210
We'll now have a closer look at this matrix as promised.
3
00:00:06,210 --> 00:00:10,290
So what we just found out by the way is that this part here
4
00:00:10,290 --> 00:00:15,280
anything you can do on a non-deterministic RAM in polynomial time
5
00:00:15,280 --> 00:00:19,060
can also be one on a deterministic RAM in exponential time.
6
00:00:19,060 --> 00:00:24,240
So any problem that is in this part down here would also be in this part up here.
7
00:00:24,240 --> 00:00:26,310
But since we are mainly interested in polynomial time,
8
00:00:26,310 --> 00:00:29,100
let's focus on the bottom part of this matrix for now.
9
00:00:29,100 --> 00:00:32,420
You'll come back to the full matrix in later units when we talked about
10
00:00:32,420 --> 00:00:37,850
exponential time complexity classes and remember that each of these squares
11
00:00:37,850 --> 00:00:43,260
contains all of the problems that can be solved in polynomial time.
12
00:00:43,260 --> 00:00:49,350
The left one on a deterministic RAM, and the right one on a non-deterministic RAM,
13
00:00:49,350 --> 00:00:51,080
and now, we'll give these names.
14
00:00:51,080 --> 00:00:56,990
So we'll call this complexity class here P, because those are all problems
15
00:00:56,990 --> 00:01:02,340
that are solvable in polynomial time on a deterministic RAM.
16
00:01:02,340 --> 00:01:09,260
And we'll call this here NP, because those are all problems solvable in polynomial time
17
00:01:09,260 --> 00:01:12,340
on a non-deterministic RAM.
18
00:01:12,340 --> 00:01:16,860
Of course, it wouldn't have been more consistent to call this one down here DP or something like that,
19
00:01:16,860 --> 00:01:18,920
but this is the way we named it.
20
00:01:18,920 --> 00:01:24,920
And now, what we also know is that any problem that can be solved in polynomial time
21
00:01:24,920 --> 00:01:30,330
on a deterministic RAM can also be solved in polynomial time on a non-deterministic RAM.
22
00:01:30,330 --> 00:01:35,160
We should probably rather redraw these black lines here like this because any problem
23
00:01:35,160 --> 00:01:41,270
that is contained in P is automatically also contained in NP but of course not vice versa.
24
00:01:41,270 --> 00:01:44,190
Otherwise, we would know that there is a polynomial time algorithm
25
00:01:44,190 --> 00:01:47,370
for vertex cover and the two other problems.
26
00:01:47,370 --> 00:01:50,640
So P contains all the problems that we know are easy.
27
00:01:50,640 --> 00:01:55,270
So, for example, finding the shortest path between two points in the graph
28
00:01:55,270 --> 00:02:00,310
or looking up an entry in the database multiplying two numbers and thousands of problems more.
29
00:02:00,310 --> 00:02:05,200
So basically, any algorithm you'll have come across in an introductory algorithm scores
30
00:02:05,200 --> 00:02:07,310
will fall into this category.
31
00:02:07,310 --> 00:02:13,180
And again, there are some theoretical nitty-gritty regarding optimization and decision problems here,
32
00:02:13,180 --> 00:02:15,740
but we can ignore that for the time being.
33
00:02:15,740 --> 00:02:18,950
So let's do a little quiz to summarize what you know by now.
34
00:02:18,950 --> 00:02:23,200
So given all you have learned, what can you say about P and NP?
35
00:02:23,200 --> 00:02:26,960
So I would like you to check which of these statements are true.
36
00:02:26,960 --> 00:02:31,340
The first statement is every problem in P is also contained in NP.
37
00:02:31,340 --> 00:02:37,060
The second statement is that every problem in NP is also contained in P.
38
00:02:37,060 --> 00:02:42,040
The third one is that P and NP are in fact equivalent.
39
00:02:42,040 --> 00:02:49,310
The fourth one is that it seems like NP should contain more problems than P or be larger than P,
40
00:02:49,310 --> 00:02:51,630
but we can't really say for sure.
41
00:02:51,630 --> 00:02:57,190
The fifth one is that vertex cover, independent set, and clique are contained in P.
42
00:02:57,190 --> 00:03:00,320
And the finally one is that those three problems are contained in NP.
43
00:03:00,320 --> 99:59:59,000
So please check every statement which given what we know by now you should consider to be true.
PK a#iA:SJ
J
C Unit_2.2_-_Non-deterministic_RAM/15-Polynomial_Time_Solution.en.srt1
00:00:00,000 --> 00:00:03,430
I think there are three statements where we can certainly say by now that they are true.
2
00:00:03,430 --> 00:00:08,890
We know that every problem that is in P is also contained in NP.
3
00:00:08,890 --> 00:00:12,070
This is why we drew the picture like this. So, that's obvious.
4
00:00:12,070 --> 00:00:15,810
If every problem in NP is also contained in P
5
00:00:15,810 --> 00:00:19,200
that would mean that we have a polynomial time algorithm for
6
00:00:19,200 --> 00:00:21,310
vertex cover, independent set, and clique.
7
00:00:21,310 --> 00:00:23,090
We do not know that to be true yet.
8
00:00:23,090 --> 00:00:28,090
Of course, we also don't know it to be false, but it's not something we can make a statement about.
9
00:00:28,090 --> 00:00:31,110
And since we can't make a statement about this here,
10
00:00:31,110 --> 00:00:34,890
we can also not to say that P and NP are equivalent or basically the same.
11
00:00:34,890 --> 00:00:39,960
Now, the fourth one is probably the most subjective one so of course
12
00:00:39,960 --> 00:00:43,440
it seems like NP should contain more problems than P
13
00:00:43,440 --> 00:00:48,730
simply for the reason that non-determinism is just so powerful that
14
00:00:48,730 --> 00:00:54,290
we would not expect that every problem that can be solved in polynomial time using non-determinism
15
00:00:54,290 --> 00:00:57,830
can also be solved in polynomial time on a deterministic RAM
16
00:00:57,830 --> 00:01:00,410
if you just think about how much time our simulation took
17
00:01:00,410 --> 00:01:03,140
and of course it might not be the best possible simulation
18
00:01:03,140 --> 00:01:05,200
but I think it's highly unlikely.
19
00:01:05,200 --> 00:01:10,190
We can't be sure, but that's why I wrote here it seems like NP should contain more problems
20
00:01:10,190 --> 00:01:13,750
and not stated it as a fact so that I can make a check mark here.
21
00:01:13,750 --> 00:01:17,860
Now, finally, vertex cover, independent set, and clique, if we knew that they were in P
22
00:01:17,860 --> 00:01:19,490
we would have a polynomial time algorithm.
23
00:01:19,490 --> 00:01:21,650
Can't really make that statement right now.
24
00:01:21,650 --> 00:01:25,500
And finally, vertex cover, independent set, and clique, yes they are in NP.
25
00:01:25,500 --> 00:01:27,930
We show that they can be solved in polynomial time
26
00:01:27,930 --> 99:59:59,000
if we have the wonderful and magic if better function available.
PK a#iA- 5 Unit_2.2_-_Non-deterministic_RAM/16-In_P_Or_NP.en.srt1
00:00:00,000 --> 00:00:02,750
So, let's say we have a problem that we know to be an NP
2
00:00:02,750 --> 00:00:06,450
but we're not sure if it is contained in P or not.
3
00:00:06,450 --> 00:00:09,780
In that case, there is actually only two things that could be true
4
00:00:09,780 --> 00:00:13,190
so either that problem is actually NP but we missed it
5
00:00:13,190 --> 00:00:16,440
so we simply haven't looked hard enough to find a good algorithm for it
6
00:00:16,440 --> 00:00:20,380
or that's the other possibility the problem is only contained in NP.
7
00:00:20,380 --> 00:00:25,330
So, no matter how hard we look, we will never find a polynomial time algorithm for it.
8
00:00:25,330 --> 00:00:29,820
The cool thing is that for some problems we know that they are closely related enough
9
00:00:29,820 --> 00:00:33,340
so that it's actually sufficient to decide this question here
10
00:00:33,340 --> 00:00:39,240
if we missed a polynomial time algorithm or if we just have no chance.
11
00:00:39,240 --> 00:00:43,230
It's actually sufficient to decide this question for only one of the problems.
12
00:00:43,230 --> 00:00:46,360
So for vertex cover, independent set, and clique, in the last unit,
13
00:00:46,360 --> 00:00:49,550
we found out that those problems were closely related.
14
00:00:49,550 --> 00:00:55,390
So, let's just do a little quiz to see if you remember how these problems were related to each other.
15
00:00:55,390 --> 00:00:59,290
So, let's assume we found a polynomial time algorithm for vertex cover.
16
00:00:59,290 --> 00:01:03,340
In that case, we would know for sure that vertex cover is contained in P.
17
00:01:03,340 --> 00:01:05,870
So what will be the case for independent set and clique?
18
00:01:05,870 --> 00:01:07,940
Would we also know these problems to be in P
19
00:01:07,940 --> 99:59:59,000
or would it not be possible to make such a statement?
PK b#iAbk 5 Unit_2.2_-_Non-deterministic_RAM/17-In_P_Or_NP.en.srt1
00:00:00,000 --> 00:00:05,290
And the answer here, of course, is that if we had a polynomial time algorithm for vertex cover,
2
00:00:05,290 --> 00:00:09,030
then as we saw in the last unit we would also have a polynomial time algorithm
3
00:00:09,030 --> 00:00:13,700
for independent set and we would have one for clique because as we found out
4
00:00:13,700 --> 00:00:18,930
solving vertex cover on a graph is basically the same problem as solving independent set.
5
00:00:18,930 --> 00:00:24,340
And if you have a good algorithm or a polynomial time algorithm for independent set,
6
00:00:24,340 --> 99:59:59,000
then through an easy transformation of the graph you can also solve clique.
PK c#iAR<
<
9 Unit_2.2_-_Non-deterministic_RAM/18-All_In_P_Or_NP.en.srt1
00:00:00,000 --> 00:00:05,850
So our three problems are so closely related that either all of them lie here in NP but not in P
2
00:00:05,850 --> 00:00:07,900
or all of them lie in P.
3
00:00:07,900 --> 00:00:10,850
We don't know which one it is but it can't be the case that,
4
00:00:10,850 --> 00:00:14,980
for example, we have just vertex cover in P and the other two problems here in NP.
5
00:00:14,980 --> 00:00:16,800
And how did we show that in the last unit?
6
00:00:16,800 --> 00:00:22,860
For clique and independent set, we showed that there was a polynomial time algorithm
7
00:00:22,860 --> 00:00:28,010
that could take a graph that was an input to independent set
8
00:00:28,010 --> 00:00:32,229
and transform that into a graph that we can use as an input for clique,
9
00:00:32,229 --> 00:00:35,440
and once we have solved the clique problem on the transformed graph,
10
00:00:35,440 --> 00:00:39,240
that same solution is also the best possible solution to independent set.
11
00:00:39,240 --> 00:00:44,480
So we have a polynomial time algorithm, so the algorithm transforms the input of one problem,
12
00:00:44,480 --> 00:00:49,060
say X, into an input of another problem, Y.
13
00:00:49,060 --> 00:00:55,330
So, for example, we take independent set and transform that graph into an input for clique
14
00:00:55,330 --> 00:00:59,380
and now you'll see one of the advantages of working with decision problems
15
00:00:59,380 --> 00:01:03,880
because the third condition is rather easy to state because we can now simply say that
16
00:01:03,880 --> 00:01:08,770
solving the problem Y on the transformed input yields the same answer
17
00:01:08,770 --> 00:01:11,950
as solving the original problem on the original input.
18
00:01:11,950 --> 00:01:15,590
So these three statements here are the same thing that you have seen in the last unit.
19
00:01:15,590 --> 00:01:19,720
So, we took an input which was a graph to independent set
20
00:01:19,720 --> 00:01:25,410
then transformed it into an input for clique and we found out that if we solve clique on that new input,
21
00:01:25,410 --> 00:01:28,980
then we would get the same answer that we would've gotten
22
00:01:28,980 --> 00:01:32,670
if we had solved independent set directly on the original input.
23
00:01:32,670 --> 00:01:35,580
And of course we also saw that the transformation works in the other way,
24
00:01:35,580 --> 00:01:39,540
so we could transform an input to clique into an input of independent set
25
00:01:39,540 --> 00:01:43,430
and now for a vertex cover and independent set, it was even easier
26
00:01:43,430 --> 00:01:47,920
because we didn't even have to transform the input, so basically the transformation was,
27
00:01:47,920 --> 00:01:53,260
we could keep the input as it is, the only thing is if we're working with the decision problem,
28
00:01:53,260 --> 00:01:58,930
of course, the answer will be a little bit different, so if we have a vertex cover of size k
29
00:01:58,930 --> 00:02:02,880
for a graph with N vertices, then for independent set,
30
00:02:02,880 --> 00:02:06,260
we must ask if we have an independent set of size n-k.
31
00:02:06,260 --> 99:59:59,000
But other than that, the transformation here is very easy.
PK T#iAYa9 9 = Unit_2.2_-_Non-deterministic_RAM/01-Gathering_Evidence.en.srtPK U#iAY̦b F Unit_2.2_-_Non-deterministic_RAM/02-Gathering_Evidence_Solution.en.srtPK V#iA$i 4 Unit_2.2_-_Non-deterministic_RAM/03-if-better.en.srtPK V#iAi8tD D F * Unit_2.2_-_Non-deterministic_RAM/04-Vertex_Cover_With_if-better.en.srtPK W#iA_j j F 4 Unit_2.2_-_Non-deterministic_RAM/05-Vertex_Cover_With_if-better.en.srtPK X#iA8B:
:
= Q; Unit_2.2_-_Non-deterministic_RAM/06-Complexity_Classes.en.srtPK Y#iA) F E Unit_2.2_-_Non-deterministic_RAM/07-Complexity_Classes_Solution.en.srtPK Z#iA ?l l ; L Unit_2.2_-_Non-deterministic_RAM/08-Two_Types_Of_RAM.en.srtPK [#iAs! ! ; ^ Unit_2.2_-_Non-deterministic_RAM/09-Two_Types_Of_RAM.en.srtPK [#iAZ) ) K .a Unit_2.2_-_Non-deterministic_RAM/10-Building_A_Non-Deterministic_Ram.en.srtPK \#iAUHJ K { Unit_2.2_-_Non-deterministic_RAM/11-Building_A_Non-Deterministic_Ram.en.srtPK ]#iAg M Unit_2.2_-_Non-deterministic_RAM/12-Simulating_A_Non-Deterministic_Ram.en.srtPK ]#iA6P7 M Unit_2.2_-_Non-deterministic_RAM/13-Simulating_A_Non-Deterministic_Ram.en.srtPK `#iA5_V : Unit_2.2_-_Non-deterministic_RAM/14-Polynomial_Time.en.srtPK a#iA:SJ
J
C * Unit_2.2_-_Non-deterministic_RAM/15-Polynomial_Time_Solution.en.srtPK a#iA- 5 շ Unit_2.2_-_Non-deterministic_RAM/16-In_P_Or_NP.en.srtPK b#iAbk 5 Unit_2.2_-_Non-deterministic_RAM/17-In_P_Or_NP.en.srtPK c#iAR<
<
9 Unit_2.2_-_Non-deterministic_RAM/18-All_In_P_Or_NP.en.srtPK