PK o#iA K Unit_2.4_-_Proof_of_SAT_(Optional)/01-Algorithms_To_Boolean_Formulae.en.srt1
00:00:00,000 --> 00:00:03,000
So how can we take an algorithm and put that into a Boolean formula?
2
00:00:03,000 --> 00:00:06,000
Well, that's where Cook and Levin had another ingenious idea,
3
00:00:06,000 --> 00:00:09,000
because they said you can look at an algorithm
4
00:00:09,000 --> 00:00:12,000
running on a RAM as a series of snapshots,
5
00:00:12,000 --> 00:00:14,000
and what I mean by this is the following:
6
00:00:14,000 --> 00:00:16,000
So assume you have an algorithm on a
7
00:00:16,000 --> 00:00:19,000
non-deterministic RAM that runs in polynomial time,
8
00:00:19,000 --> 00:00:23,000
so you have a point in time T equals 0, that's when your algorithm starts out,
9
00:00:23,000 --> 00:00:28,000
then you have T equals 1, T equals 2, so those are the time steps here.
10
00:00:28,000 --> 00:00:32,000
And the final time step is going to be some polynomial of N.
11
00:00:32,000 --> 00:00:35,000
That is clear because we're looking at an algorithm
12
00:00:35,000 --> 00:00:37,000
that solves a problem that lies in NP,
13
00:00:37,000 --> 00:00:42,000
So that means it only takes polynomial time on a non-deterministic RAM at least.
14
00:00:42,000 --> 00:00:46,000
Now if you look at what happens on the RAM in each time step,
15
00:00:46,000 --> 00:00:48,000
I can basically draw you the following picture.
16
00:00:48,000 --> 00:00:50,000
If you recall from unit one what the RAM looks like,
17
00:00:50,000 --> 00:00:52,000
the RAM has only a few components.
18
00:00:52,000 --> 00:00:55,000
The RAM has a read-only memory,
19
00:00:55,000 --> 00:00:58,000
the RAM has a program or the algorithm running,
20
00:00:58,000 --> 00:01:01,000
so this algorithm here is basically the program running,
21
00:01:01,000 --> 00:01:05,000
and just as I would write the algorithm line by line by line,
22
00:01:05,000 --> 00:01:07,000
I can also write it in this way,
23
00:01:07,000 --> 00:01:09,000
so this here would be the first line of code,
24
00:01:09,000 --> 00:01:12,000
then this would be the second line of code, and so on.
25
00:01:12,000 --> 00:01:15,000
And finally, the RAM had a reading and writing memory,
26
00:01:15,000 --> 00:01:19,000
so we had some memory cells here holding the variables,
27
00:01:19,000 --> 00:01:21,000
and those variables, of course, are changed by the program
28
00:01:21,000 --> 00:01:24,000
depending on what's here in the input.
29
00:01:24,000 --> 00:01:26,000
And now comes the neat part that Cook and Levin observed,
30
00:01:26,000 --> 00:01:29,000
because what they observed is
31
00:01:29,000 --> 00:01:32,000
that when you look at an algorithm working on the RAM,
32
00:01:32,000 --> 00:01:37,000
then you can depict that as a number of these snapshots,
33
00:01:37,000 --> 00:01:42,000
so if you say, add T equals 0,
34
00:01:42,000 --> 00:01:45,000
these are the contents of the read-only memory.
35
00:01:45,000 --> 00:01:48,000
This is, actually we need other information,
36
00:01:48,000 --> 00:01:50,000
we also needs to know where the program is at,
37
00:01:50,000 --> 00:01:52,000
but you can basically say, this is the input here,
38
00:01:52,000 --> 00:01:56,000
this is the program, and this is the line of the program that we're executing right now,
39
00:01:56,000 --> 00:01:59,000
and this here is the contents of the read/write memory.
40
00:01:59,000 --> 00:02:02,000
In the beginning this will be empty,
41
00:02:02,000 --> 00:02:05,000
but as the algorithm works, it will also put some content in here,
42
00:02:05,000 --> 00:02:07,000
and then, of course, the program moves on.
43
00:02:07,000 --> 00:02:10,000
It can also jump back and forth here,
44
00:02:10,000 --> 00:02:14,000
and of course, we will have more and more content in the memory,
45
00:02:14,000 --> 00:02:19,000
and at a certain point in time the program will say, I'm done,
46
00:02:19,000 --> 00:02:21,000
and it will hopefully have a certain output here.
47
00:02:21,000 --> 00:02:23,000
But since we're working with decision problems,
48
00:02:23,000 --> 00:02:29,000
actually it's only interesting to us if the program says, yes or no at the end.
49
00:02:29,000 --> 00:02:33,000
So for decision problems we don't even really care about what's in here,
50
00:02:33,000 --> 00:02:37,000
we would care about that if we were solving the optimization problem
51
00:02:37,000 --> 00:02:39,000
or want additional information,
52
00:02:39,000 --> 00:02:41,000
but actually for a decision problem,
53
00:02:41,000 --> 00:02:43,000
it would just be important for us to know
54
00:02:43,000 --> 00:02:46,000
at which line of code the algorithm finishes.
55
00:02:46,000 --> 00:02:50,000
If it finishes at a return statement that will return yes to us
56
00:02:50,000 --> 00:02:54,000
or a return statement that will return no to us.
57
00:02:54,000 --> 00:02:57,000
Now let's have a closer look at those snapshots,
58
00:02:57,000 --> 00:02:59,000
and we'll actually do that as a quiz.
59
00:02:59,000 --> 00:03:02,000
So this here is one snapshot.
60
00:03:02,000 --> 00:03:07,000
I would like you to tell me what we can say about a single snapshot
61
00:03:07,000 --> 00:03:11,000
and also about all of these snapshots here.
62
00:03:11,000 --> 00:03:13,000
So there are 3 statements,
63
00:03:13,000 --> 00:03:16,000
each of which I would like you to check this box if you think they are true
64
00:03:16,000 --> 00:03:18,000
and otherwise leave it blank.
65
00:03:18,000 --> 00:03:23,000
So the first claim you could make is that each snapshot has size polynomial in N,
66
00:03:23,000 --> 00:03:26,000
and N is the size of the input as always.
67
00:03:26,000 --> 00:03:29,000
Secondly, you could claim that there can be
68
00:03:29,000 --> 00:03:33,000
an exponential number of snapshots if we look at all of the time steps.
69
00:03:33,000 --> 00:03:37,000
And finally, one claim that I would like you to check out as well is
70
00:03:37,000 --> 00:03:40,000
all snapshots, if taken together,
71
00:03:40,000 --> 00:03:43,000
so this whole part here,
72
00:03:43,000 --> 00:03:45,000
have polynomial size,
73
00:03:45,000 --> 00:03:47,000
and by polynomial size, I again mean that it's some
74
00:03:47,000 --> 00:03:50,000
polynomial of the input size that we're always using.
75
00:03:50,000 --> 00:03:52,000
You should keep in mind that the algorithm
76
00:03:52,000 --> 00:03:56,000
that we're looking at is an algorithm for a problem in NP,
77
00:03:56,000 --> 99:59:59,000
and it runs on a non-deterministic RAM.
PK p#iAC,
T Unit_2.4_-_Proof_of_SAT_(Optional)/02-Algorithms_To_Boolean_Formulae_Solution.en.srt1
00:00:00,000 --> 00:00:02,000
So there's 2 true answers here,
2
00:00:02,000 --> 00:00:04,000
and I know this was a rather challenging question,
3
00:00:04,000 --> 00:00:07,000
but just imagine how challenging it must have been for Cook and Levin
4
00:00:07,000 --> 00:00:10,000
when they figured this out for the first time.
5
00:00:10,000 --> 00:00:13,000
So first of all, each snapshot has size polynomial and N.
6
00:00:13,000 --> 00:00:16,000
That is true, so why is that?
7
00:00:16,000 --> 00:00:21,000
Well, first of all, we said the size of the input is a polynomial of N
8
00:00:21,000 --> 00:00:24,000
or often times it is N, but sometimes it can also be a polynomial.
9
00:00:24,000 --> 00:00:28,000
So for example, when we are given a graph with N vertices,
10
00:00:28,000 --> 00:00:30,000
then there can be up to N squared edges,
11
00:00:30,000 --> 00:00:33,000
but in any case, the input is some polynomial of N.
12
00:00:33,000 --> 00:00:37,000
Now the size of the algorithm or program here,
13
00:00:37,000 --> 00:00:42,000
that is constant because the algorithm doesn't change with the input,
14
00:00:42,000 --> 00:00:46,000
so we can assume that this year has constant size
15
00:00:46,000 --> 00:00:48,000
no matter what kind of input we are given.
16
00:00:48,000 --> 00:00:50,000
And then finally, this is an interesting one,
17
00:00:50,000 --> 00:00:52,000
how much memory does our algorithm need?
18
00:00:52,000 --> 00:00:56,000
Well, it's an algorithm for a problem in NP,
19
00:00:56,000 --> 00:00:59,000
which means it takes only a polynomial number of time steps,
20
00:00:59,000 --> 00:01:02,000
and in each time step,
21
00:01:02,000 --> 00:01:05,000
it can only modify a constant amount of variables.
22
00:01:05,000 --> 00:01:08,000
So the total memory that it needs
23
00:01:08,000 --> 00:01:11,000
is some constant times the number of time steps,
24
00:01:11,000 --> 00:01:14,000
and since the number of time steps is a polynomial of N,
25
00:01:14,000 --> 00:01:19,000
the total space required here for the memory is also a polynomial of N.
26
00:01:19,000 --> 00:01:21,000
So you have a polynomial of N
27
00:01:21,000 --> 00:01:24,000
plus some constant plus a polynomial of N,
28
00:01:24,000 --> 00:01:28,000
so each single snapshot has size polynomial in N.
29
00:01:28,000 --> 00:01:30,000
Now the second one, I think that was the easiest one to find out,
30
00:01:30,000 --> 00:01:32,000
is of course not true
31
00:01:32,000 --> 00:01:34,000
because we said we're looking at a problem in NP,
32
00:01:34,000 --> 00:01:36,000
we should have even written it down here on the left side.
33
00:01:36,000 --> 00:01:39,000
So we said the number of time steps must be some polynomial,
34
00:01:39,000 --> 00:01:41,000
because otherwise, the problem wouldn't be an NP,
35
00:01:41,000 --> 00:01:43,000
and since we're running on a non-deterministic RAM,
36
00:01:43,000 --> 00:01:47,000
we can assume that the number of time steps here is bounded by some polynomial.
37
00:01:47,000 --> 00:01:52,000
So since there's only a polynomial number of time steps,
38
00:01:52,000 --> 00:01:55,000
there can also only be a polynomial number of snapshots,
39
00:01:55,000 --> 00:01:59,000
so there cannot be an exponential number of snapshots.
40
00:01:59,000 --> 00:02:01,000
But this, if you take it together, is--
41
00:02:01,000 --> 00:02:03,000
well, I don't know it's pretty cool,
42
00:02:03,000 --> 00:02:06,000
but at least it's very useful for the proof that we're trying to do,
43
00:02:06,000 --> 00:02:10,000
because if each snapshot has a size that's polynomial in N
44
00:02:10,000 --> 00:02:14,000
and the total number of snapshots that we have is a polynomial,
45
00:02:14,000 --> 00:02:18,000
then you have a situation where you have
46
00:02:18,000 --> 00:02:22,000
a polynomial number of polynomial size snapshots,
47
00:02:22,000 --> 00:02:26,000
which means that the size of it all taken together is
48
00:02:26,000 --> 00:02:30,000
a polynomial times a polynomial, which again is a polynomial.
49
00:02:30,000 --> 00:02:35,000
So basically, a complete protocol of what this algorithm here is doing
50
00:02:35,000 --> 00:02:38,000
given this input and using this memory here,
51
00:02:38,000 --> 00:02:42,000
the complete protocol only takes up a polynomial amount of space.
52
00:02:42,000 --> 00:02:45,000
Polynomial and N, the size of the input.
53
00:02:45,000 --> 00:02:50,000
What I will now show you is how you can encode a single snapshot.
54
00:02:50,000 --> 99:59:59,000
So for example, this one here or this one here as a Boolean formula.
PK p#iA( D Unit_2.4_-_Proof_of_SAT_(Optional)/03-Special_Boolean_Formula.en.srt1
00:00:00,000 --> 00:00:03,540
To show you how we can encode a single single snap shot on the REM
2
00:00:03,540 --> 00:00:05,300
as a Boolean formula,
3
00:00:05,300 --> 00:00:08,020
I'm going to show you a little trick with the Boolean formula.
4
00:00:08,020 --> 00:00:10,800
So this Boolean formula--
5
00:00:10,800 --> 00:00:13,660
it looks a bit intimidating, and it doesn't look fun.
6
00:00:13,660 --> 00:00:16,820
Well I'll just quickly explain it to you and then help you figure out
7
00:00:16,820 --> 00:00:19,170
the special property that it has.
8
00:00:19,170 --> 00:00:22,450
So the formula consists of 6 variables:
9
00:00:22,450 --> 00:00:26,190
X1, X2, X3 to X6
10
00:00:26,190 --> 00:00:29,090
and it has 7 brackets,
11
00:00:29,090 --> 00:00:32,220
so as you can see, each of those brackets contains
12
00:00:32,220 --> 00:00:35,880
all of the 6 variables: X1, X2, X3, X4, X5, X6.
13
00:00:35,880 --> 00:00:37,900
Sometimes they're a bit mixed up,
14
00:00:37,900 --> 00:00:42,500
but every bracket here contains the 6 variables exactly once.
15
00:00:42,500 --> 00:00:45,040
They're all connected with an and here,
16
00:00:45,040 --> 00:00:46,990
and each one of them looks like this,
17
00:00:46,990 --> 00:00:49,960
so up here you have an or over all of those variables,
18
00:00:49,960 --> 00:00:51,360
and down here,
19
00:00:51,360 --> 00:00:53,390
each bracket has a very similar structure,
20
00:00:53,390 --> 00:00:55,620
so you have X1
21
00:00:55,620 --> 00:00:58,020
or you have one of the variables
22
00:00:58,020 --> 00:01:00,400
and a not of that variable,
23
00:01:00,400 --> 00:01:02,060
or,
24
00:01:02,060 --> 00:01:05,230
and this is a very big not
25
00:01:05,230 --> 00:01:07,340
over off the other variables,
26
00:01:07,340 --> 00:01:09,230
and those are combined by or.
27
00:01:09,230 --> 00:01:12,810
Now probably it's a bit tough to figure out by yourself
28
00:01:12,810 --> 00:01:14,840
what the purpose of this formula is.
29
00:01:14,840 --> 00:01:16,650
I want you to figure it out,
30
00:01:16,650 --> 00:01:18,490
but I will give you a few choices.
31
00:01:18,490 --> 00:01:21,440
So what's special about this Boolean formula?
32
00:01:21,440 --> 00:01:24,530
Does it not have any satisfying assignment?
33
00:01:24,530 --> 00:01:26,940
Does it have several satisfying assignments?
34
00:01:26,940 --> 00:01:29,650
Can it only be satisfied if exactly
35
00:01:29,650 --> 00:01:32,440
one of those 6 variables is set to true,
36
00:01:32,440 --> 00:01:34,270
and finally, if you generalize this,
37
00:01:34,270 --> 00:01:37,520
so not 6 variables but any number n of variables,
38
00:01:37,520 --> 00:01:39,970
and then you do the same structure as you do here.
39
00:01:39,970 --> 00:01:41,630
That's the whole resulting formula,
40
00:01:41,630 --> 00:01:44,280
have size 0 (n squared) for n variables?
41
00:01:44,280 --> 00:01:47,630
So I think by now you're used to more than one of these answers
42
00:01:47,630 --> 99:59:59,000
can be true, so check all of these that are correct.
PK q#iA M Unit_2.4_-_Proof_of_SAT_(Optional)/04-Special_Boolean_Formula_Solution.en.srt1
00:00:00,000 --> 00:00:02,210
And the answer here is not actually
2
00:00:02,210 --> 00:00:05,130
3 of those statements, those 3 down here are correct.
3
00:00:05,130 --> 00:00:07,890
I'll explain them in a minute, and this one here is not correct.
4
00:00:07,890 --> 00:00:12,060
So the formula indeed does have a satisfying assignment.
5
00:00:12,060 --> 00:00:15,260
Not only one; it actually has several satisfying assignments,
6
00:00:15,260 --> 00:00:18,090
but each of those assignments has the property that
7
00:00:18,090 --> 00:00:20,670
exactly one variable is set to true,
8
00:00:20,670 --> 00:00:23,240
and I'll show you in a second how that works.
9
00:00:23,240 --> 00:00:26,740
And of course--I mean, the last thing was probably quite easy to figure out;
10
00:00:26,740 --> 00:00:29,730
as you see this already has kind of a square shape,
11
00:00:29,730 --> 00:00:32,980
so if we continue like this and add another variable here,
12
00:00:32,980 --> 00:00:36,090
then we would have to add another line down here,
13
00:00:36,090 --> 00:00:38,790
and each of those formulas grows by 1 and
14
00:00:38,790 --> 00:00:41,860
the whole thing grows by one of those brackets here
15
00:00:41,860 --> 00:00:43,860
for each variable that we add,
16
00:00:43,860 --> 00:00:47,630
so the size is O(n squared) for n variables.
17
00:00:47,630 --> 00:00:50,050
So let me explain this here to you.
18
00:00:50,050 --> 00:00:53,250
So there are several satisfying assignments,
19
00:00:53,250 --> 00:00:55,850
but each of those satisfying assignments has the property
20
00:00:55,850 --> 00:00:58,500
that exactly 1 variable is true.
21
00:00:58,500 --> 00:01:01,010
So for example, let's say that we set
22
00:01:01,010 --> 00:01:03,530
X1 to true,
23
00:01:03,530 --> 00:01:06,000
then what will happen is the following,
24
00:01:06,000 --> 00:01:11,020
so X1 is true; this means this one down here goes to 0.
25
00:01:11,020 --> 00:01:14,630
This one goes to 1, this one goes to 1, this one goes to 1,
26
00:01:14,630 --> 00:01:16,610
this one goes to 1, and this one is 1.
27
00:01:16,610 --> 00:01:18,530
So let's have a look here
28
00:01:18,530 --> 00:01:21,080
at this part of the formula.
29
00:01:21,080 --> 00:01:23,920
All of the variables here are connected by an or,
30
00:01:23,920 --> 00:01:27,990
so we have X1 or X3 or X4 or X5 or X6.
31
00:01:27,990 --> 00:01:30,710
This means if just one of the variables here
32
00:01:30,710 --> 00:01:32,410
is set to true,
33
00:01:32,410 --> 00:01:34,060
which it now is,
34
00:01:34,060 --> 00:01:37,060
then the whole bracket here,
35
00:01:37,060 --> 00:01:39,810
so from here to here will also evaluate to true,
36
00:01:39,810 --> 00:01:43,390
and then we take this very, very big not here,
37
00:01:43,390 --> 00:01:46,230
which means this will evaluate to 0.
38
00:01:46,230 --> 00:01:49,160
Now this very big not here evaluates to 0,
39
00:01:49,160 --> 00:01:51,900
then we have to make sure that this variable here
40
00:01:51,900 --> 00:01:53,960
evaluates to 1,
41
00:01:53,960 --> 00:01:56,250
because all of them are connected by an and,
42
00:01:56,250 --> 00:01:58,290
and we are looking for a satisfying assignment,
43
00:01:58,290 --> 00:02:01,290
so to do that, we have to set X2 to 0
44
00:02:01,290 --> 00:02:04,450
so that this here evaluates to 1.
45
00:02:04,450 --> 00:02:06,890
Now for the next bracket, it works the same way,
46
00:02:06,890 --> 00:02:09,830
because again, we have X1 set to true,
47
00:02:09,830 --> 00:02:11,850
so the bracket evaluates to true,
48
00:02:11,850 --> 00:02:13,670
so the not evaluates to 0,
49
00:02:13,670 --> 00:02:16,320
and so again we have to set this to 1
50
00:02:16,320 --> 00:02:18,000
which means X3 is 1
51
00:02:18,000 --> 00:02:21,040
and we can go on through this the same way.
52
00:02:21,040 --> 00:02:26,550
So the formula forces us to set every variable except for X1 to false,
53
00:02:26,550 --> 00:02:28,340
and now the way that this formula is structured, of course,
54
00:02:28,340 --> 00:02:32,130
we could also have chosen to set X2 to true,
55
00:02:32,130 --> 00:02:34,400
but then if X2 is set to true,
56
00:02:34,400 --> 00:02:40,220
we have this here, so X2 here is 1, 1, 1, 1,
57
00:02:40,220 --> 00:02:44,000
which means in order to get these here to go to 1,
58
00:02:44,000 --> 00:02:47,310
so we need to have these here go to 1,
59
00:02:47,310 --> 00:02:50,960
because this here evaluates to 0, 0, 0, 0, 0,
60
00:02:50,960 --> 00:02:54,440
so we have to set all of these variables here to false.
61
00:02:54,440 --> 00:02:56,090
Yeah, finally, what about this one here?
62
00:02:56,090 --> 00:02:59,800
Well, since X2 is set to true,
63
00:02:59,800 --> 00:03:02,240
not X2 is set to false,
64
00:03:02,240 --> 00:03:05,700
but luckily, because we've set all of the variables to false,
65
00:03:05,700 --> 00:03:08,700
so we have 0, 0, 0, 0, 0.
66
00:03:08,700 --> 00:03:11,900
In this case, the large not here
67
00:03:11,900 --> 00:03:13,330
evaluates to true,
68
00:03:13,330 --> 00:03:15,910
so this bracket here also evaluates to true,
69
00:03:15,910 --> 99:59:59,000
and we have satisfied the Boolean formula.
PK r#iAa# # 6 Unit_2.4_-_Proof_of_SAT_(Optional)/05-Snapshots.en.srt1
00:00:00,000 --> 00:00:02,980
What this means is not for any given number of variables,
2
00:00:02,980 --> 00:00:05,030
we can write a Boolean formula
3
00:00:05,030 --> 00:00:08,430
that can be satisfied
4
00:00:08,430 --> 00:00:12,530
if and only if exactly what one of these variables is set to true,
5
00:00:12,530 --> 00:00:16,110
and we figure out that we can do this for any number of variables that we want.
6
00:00:16,110 --> 00:00:19,640
So now let's go back to snapshots
7
00:00:19,640 --> 00:00:22,230
and see what the Boolean formula
8
00:00:22,230 --> 00:00:25,090
that I just showed you has to do with these snapshots.
9
00:00:25,090 --> 00:00:28,130
Each snapshot, as we've said, basically consists of
10
00:00:28,130 --> 00:00:30,840
3 components, so we have the read only number here,
11
00:00:30,840 --> 00:00:32,119
which is basically the input.
12
00:00:32,119 --> 00:00:35,390
We have program, and we have the read-write memory
13
00:00:35,390 --> 00:00:38,200
for immediate results and output.
14
00:00:38,200 --> 00:00:43,330
So now let's think back a moment of how we defined the RAM.
15
00:00:43,330 --> 00:00:45,740
When we defined the RAM in the last unit,
16
00:00:45,740 --> 00:00:47,370
what we said was the following.
17
00:00:47,370 --> 00:00:50,230
We said that whenever we're talking about memory,
18
00:00:50,230 --> 00:00:52,480
so this part here or this part here,
19
00:00:52,480 --> 00:00:55,450
then every single cell in the memory can not hold
20
00:00:55,450 --> 00:00:57,920
arbitrarily large variables,
21
00:00:57,920 --> 00:00:59,720
which means, for example, that
22
00:00:59,720 --> 00:01:02,100
this cell here could either be 0;
23
00:01:02,100 --> 00:01:05,040
it could be 1, it could be 2, and so on,
24
00:01:05,040 --> 00:01:08,490
but there's a certain limit of how large those values here can be,
25
00:01:08,490 --> 00:01:11,330
just as with your novel computer programs, too.
26
00:01:11,330 --> 00:01:13,630
They can carry very, very large numbers
27
00:01:13,630 --> 00:01:15,090
but there's a limit
28
00:01:15,090 --> 00:01:17,230
and that limit is some constant,
29
00:01:17,230 --> 00:01:20,310
so I'll just write c here, so if you have an 8-bit computer,
30
00:01:20,310 --> 00:01:23,270
that constant will be smaller, of course, than if you have a 16-bit computer
31
00:01:23,270 --> 00:01:25,360
and so on, but in any case,
32
00:01:25,360 --> 00:01:28,010
it will be some constant determined by the machine,
33
00:01:28,010 --> 00:01:30,800
and the same thing is going to be true all along the memory.
34
00:01:30,800 --> 00:01:33,850
So for each single memory cell
35
00:01:33,850 --> 00:01:35,600
that you have here,
36
00:01:35,600 --> 00:01:37,650
you have a constant number of possibilities
37
00:01:37,650 --> 00:01:40,050
for the values that this memory cell can take,
38
00:01:40,050 --> 00:01:43,250
so the size here is constant,
39
00:01:43,250 --> 00:01:45,170
and here, it's polynomial in n,
40
00:01:45,170 --> 00:01:46,850
as we figured out before.
41
00:01:46,850 --> 00:01:48,320
Now what about the program?
42
00:01:48,320 --> 00:01:50,470
So for the program, we said that,
43
00:01:50,470 --> 00:01:53,150
of course the size of the program of the algorithm
44
00:01:53,150 --> 00:01:56,110
does not change with the size of the input,
45
00:01:56,110 --> 00:01:59,250
so if you look at the program and your write it
46
00:01:59,250 --> 00:02:02,790
as we said, we've written the code from left to right,
47
00:02:02,790 --> 00:02:04,810
but normally, you'll write it from top to bottom,
48
00:02:04,810 --> 00:02:07,270
so if you took this code and wrote it like this,
49
00:02:07,270 --> 00:02:11,490
then you would have a constant number of lines in your program
50
00:02:11,490 --> 00:02:14,240
and that would be a certain position on where you are,
51
00:02:14,240 --> 00:02:16,290
so again here,
52
00:02:16,290 --> 00:02:19,810
there's a constant number of potential positions where you can be in the code,
53
00:02:19,810 --> 00:02:21,800
and of course, you just have one code,
54
00:02:21,800 --> 00:02:24,350
so there's no polynomial size here.
55
00:02:24,350 --> 00:02:27,120
It's just a constant number of code lines.
56
00:02:27,120 --> 00:02:29,590
And finally, over here fr the input;
57
00:02:29,590 --> 00:02:32,440
of course this is read only, but what I'm interested in
58
00:02:32,440 --> 00:02:35,680
is again the possible number of states
59
00:02:35,680 --> 00:02:37,720
that you can have in each of these memory cells,
60
00:02:37,720 --> 00:02:40,710
and that again is the same constant as over here,
61
00:02:40,710 --> 00:02:44,000
and here we have again a polynomial in n,
62
00:02:44,000 --> 00:02:48,890
so what does this have to do with the Boolean formula that I just showed you?
63
00:02:48,890 --> 00:02:52,610
Well, what we could do is turn this into a Boolean formula
64
00:02:52,610 --> 00:02:54,400
with a huge number of variables,
65
00:02:54,400 --> 00:02:57,760
but you will see that the number of variables is still polynomial.
66
00:02:57,760 --> 00:03:00,080
So what are my variables going to be?
67
00:03:00,080 --> 00:03:02,920
I'm going to have one variable
68
00:03:02,920 --> 00:03:06,860
for each of those black boxes here
69
00:03:06,860 --> 00:03:09,110
and also one variable for each of these here,
70
00:03:09,110 --> 00:03:11,850
and so on, and so on, and so on.
71
00:03:11,850 --> 00:03:13,230
I'm going to have
72
00:03:13,230 --> 00:03:17,930
one variable for all of the possibilities
73
00:03:17,930 --> 00:03:20,150
where I could be in my program code,
74
00:03:20,150 --> 00:03:23,920
and again here I'm going to do the same thing as I did here on the left side.
75
00:03:23,920 --> 00:03:26,950
I will have one Boolean variable
76
00:03:26,950 --> 00:03:29,220
for each of those possibilities,
77
00:03:29,220 --> 00:03:32,180
and what one of those Boolean variables means is
78
00:03:32,180 --> 00:03:34,750
basically--or what I want it to mean is
79
00:03:34,750 --> 00:03:36,710
if it's set to true,
80
00:03:36,710 --> 00:03:39,450
it tells me that
81
00:03:39,450 --> 00:03:41,440
a memory cell contains that value,
82
00:03:41,440 --> 00:03:44,780
so if this variable here is set to true,
83
00:03:44,780 --> 00:03:49,480
I want that memory cell up here to contain the value 0.
84
00:03:49,480 --> 00:03:52,990
If it's set to 1, I want this one here to contain the value 1.
85
00:03:52,990 --> 00:03:58,140
If it's set to 2, I want this one here to have the value 2, and so on.
86
00:03:58,140 --> 00:04:02,120
And now you see why the Boolean formula that I just showed you
87
00:04:02,120 --> 00:04:06,700
where you can force just exactly one single variable to be true
88
00:04:06,700 --> 00:04:08,530
is useful in this case,
89
00:04:08,530 --> 00:04:11,640
because if I put all of these variables here
90
00:04:11,640 --> 00:04:13,970
into such a Boolean formula,
91
00:04:13,970 --> 00:04:16,620
I would have a Boolean formula that can be satisfied
92
00:04:16,620 --> 00:04:18,329
if and only if
93
00:04:18,329 --> 00:04:21,040
exactly one of those variables here is true,
94
00:04:21,040 --> 00:04:23,700
so it tells me
95
00:04:23,700 --> 00:04:26,300
uniquely what goes into this memory cell here
96
00:04:26,300 --> 00:04:28,400
as long as it's satisfied,
97
00:04:28,400 --> 00:04:31,400
and the same thing over here, and over here, and over here.
98
00:04:31,400 --> 00:04:33,310
And now
99
00:04:33,310 --> 00:04:37,270
if I write this Boolean formula for this memory cell here,
100
00:04:37,270 --> 00:04:41,090
I write it for this memory cell here, here of course also,
101
00:04:41,090 --> 00:04:43,290
and so on,
102
00:04:43,290 --> 00:04:46,040
and if I combine all of those Boolean formulas,
103
00:04:46,040 --> 00:04:47,860
so I have a Boolean formula here,
104
00:04:47,860 --> 00:04:50,490
I have a Boolean formula here,
105
00:04:50,490 --> 00:04:52,980
I have one here,
106
00:04:52,980 --> 00:04:55,270
from this column,
107
00:04:55,270 --> 00:04:57,400
from this column,
108
00:04:57,400 --> 00:04:59,530
from this column, and so on.
109
00:04:59,530 --> 00:05:01,620
So I have Boolean formula,
110
00:05:01,620 --> 00:05:03,240
and then I do an and,
111
00:05:03,240 --> 00:05:05,670
and I have the next Boolean formula, and I have an and,
112
00:05:05,670 --> 00:05:08,960
and I have the next Boolean formula,
113
00:05:08,960 --> 00:05:12,820
and I continue doing this, and I will also do this here for the program.
114
00:05:12,820 --> 99:59:59,000
And of course, I will get a very, very, very large Boolean formula.
PK s#iANhz* * J Unit_2.4_-_Proof_of_SAT_(Optional)/06-Properties_Of_Boolean_Formula.en.srt1
00:00:00,000 --> 00:00:03,150
And this is, I promise, going to be the most
2
00:00:03,150 --> 00:00:05,140
complicated part of this unit.
3
00:00:05,140 --> 00:00:07,010
Once you've understood this,
4
00:00:07,010 --> 00:00:09,070
you have understood how to prove the Cook-Levin theorums,
5
00:00:09,070 --> 00:00:11,290
so bear with me for another minute here.
6
00:00:11,290 --> 00:00:13,700
If we write this huge Boolean formula
7
00:00:13,700 --> 00:00:16,190
what I would like to ask you now is
8
00:00:16,190 --> 00:00:19,670
what properties this Boolean formula has.
9
00:00:19,670 --> 00:00:23,610
So if I write a big Boolean formula like this here,
10
00:00:23,610 --> 00:00:26,050
so the train that's exactly one variable here
11
00:00:26,050 --> 00:00:29,270
is set to true one here, one here, and so on and so on.
12
00:00:29,270 --> 00:00:32,350
What I would like you to think about is
13
00:00:32,350 --> 00:00:36,140
some of the properties that this Boolean formula will have.
14
00:00:36,140 --> 00:00:39,340
So there are 3 properties of 3 choices that I'm giving you.
15
00:00:39,340 --> 00:00:44,130
One is that the size of this Boolean formula here is polynomial in in.
16
00:00:44,130 --> 00:00:46,140
The second one is
17
00:00:46,140 --> 00:00:50,430
that this Boolean formula here has only a single satisfying assignment.
18
00:00:50,430 --> 00:00:54,160
And the third one is that every satisfying assignment
19
00:00:54,160 --> 00:00:56,350
of this Boolean formula
20
00:00:56,350 --> 00:00:58,200
presents a potential snapshot,
21
00:00:58,200 --> 00:01:01,840
so it kind of uniquely defines what the memory of the RAM looks like
22
00:01:01,840 --> 00:01:04,040
and where the program is at.
23
00:01:04,040 --> 00:01:06,160
Now of course, there's only 3 choices here;
24
00:01:06,160 --> 00:01:09,130
again, more than 1 can be true and you could
25
00:01:09,130 --> 00:01:11,510
make your way through by guessing,
26
00:01:11,510 --> 00:01:14,070
but before that, I'd encourage you to think through these statements,
27
00:01:14,070 --> 00:01:16,960
because once you understand this part,
28
00:01:16,960 --> 99:59:59,000
the rest of the Cook-Levin theory is actually quite easy.
PK t#iA@ S Unit_2.4_-_Proof_of_SAT_(Optional)/07-Properties_Of_Boolean_Formula_Solution.en.srt1
00:00:00,000 --> 00:00:02,200
And there's 2 correct answers here.
2
00:00:02,200 --> 00:00:06,080
The first one is that the size of this huge Boolean formula here
3
00:00:06,080 --> 00:00:08,910
is polynomial in n, and I will show you why.
4
00:00:08,910 --> 00:00:13,350
First of all, how large is each one of these formulas that we're building?
5
00:00:13,350 --> 00:00:17,100
Well, there's a constant number of variables
6
00:00:17,100 --> 00:00:19,300
and as I showed you before,
7
00:00:19,300 --> 00:00:22,720
if you want to ensure that for a constant number of variables,
8
00:00:22,720 --> 00:00:24,960
only exactly one of them
9
00:00:24,960 --> 00:00:26,510
can be set to true,
10
00:00:26,510 --> 00:00:28,390
then the resulting formula
11
00:00:28,390 --> 00:00:31,830
is about the square of the number of variables that you have
12
00:00:31,830 --> 00:00:33,930
and since we have a constant number of variables,
13
00:00:33,930 --> 00:00:39,010
each formula here is about the size of the square of that constant,
14
00:00:39,010 --> 00:00:41,170
so we have--
15
00:00:41,170 --> 00:00:45,080
it's kind of O of c squared, and c does not depend on the size of the inputs,
16
00:00:45,080 --> 00:00:49,860
so in a way, we can even write this as O of 1.
17
00:00:49,860 --> 00:00:52,870
Now we have a polynomial number
18
00:00:52,870 --> 00:00:55,100
of these Boolean formulas,
19
00:00:55,100 --> 00:00:58,740
so we have a polynomial n times the constant;
20
00:00:58,740 --> 00:01:00,690
this is again a polynomial of n,
21
00:01:00,690 --> 00:01:03,040
so we're fine on this side here.
22
00:01:03,040 --> 00:01:06,150
We're also fine on this side here, because the formulas again are
23
00:01:06,150 --> 00:01:08,300
of constant size;
24
00:01:08,300 --> 00:01:10,300
it can, of course, be a huge size,
25
00:01:10,300 --> 00:01:14,070
especially if you have a system that can carry very large variables,
26
00:01:14,070 --> 00:01:16,120
but nevertheless, it's a constant size,
27
00:01:16,120 --> 00:01:19,370
and that's all we care about; it does not depend on the size of the input,
28
00:01:19,370 --> 00:01:22,420
and we have a polynomial number of them again here.
29
00:01:22,420 --> 00:01:27,550
And finally, the code also has a constant number of lines,
30
00:01:27,550 --> 00:01:31,010
and so the Boolean formula resulting from that
31
00:01:31,010 --> 00:01:33,550
will also have constant size,
32
00:01:33,550 --> 00:01:35,760
so overall, this huge formula here
33
00:01:35,760 --> 00:01:38,880
has a size that is polynomial in n.
34
00:01:38,880 --> 00:01:41,530
Does this formula have only one satisfying assignment?
35
00:01:41,530 --> 00:01:45,640
No, it doesn't; it has a huge number of satisfying assignments,
36
00:01:45,640 --> 00:01:48,030
but each of those satisfying assginments
37
00:01:48,030 --> 00:01:52,460
will ensure that exactly one of the variables here is set to true and so on,
38
00:01:52,460 --> 00:01:54,950
and this gives us the third property,
39
00:01:54,950 --> 00:01:57,800
which means that this satisfying assignment
40
00:01:57,800 --> 00:02:01,920
defines a snapshot, because it will tell you exactly what's in this memory cell here
41
00:02:01,920 --> 00:02:04,180
and so on.
42
00:02:04,180 --> 00:02:06,780
It will tell you exactly where the program is at
43
00:02:06,780 --> 00:02:09,430
and it will also tell you exactly
44
00:02:09,430 --> 00:02:11,460
what's here in this memory.
45
00:02:11,460 --> 00:02:13,180
And once we have this,
46
00:02:13,180 --> 00:02:16,680
you have actually completed the most difficult step of this unit
47
00:02:16,680 --> 00:02:18,290
in my mind,
48
00:02:18,290 --> 00:02:20,670
and we are now ready to show that
49
00:02:20,670 --> 99:59:59,000
sat is np complete.
PK u#iA>A} } B Unit_2.4_-_Proof_of_SAT_(Optional)/08-A_Series_Of_Snapshots.en.srt1
00:00:00,000 --> 00:00:02,890
So now our Boolean formula that we are building
2
00:00:02,890 --> 00:00:05,950
as it inputs to SAT is going to become even larger.
3
00:00:05,950 --> 00:00:07,770
So as you have seen before,
4
00:00:07,770 --> 00:00:11,610
the calculation that a non deterministic RAM makes
5
00:00:11,610 --> 00:00:14,220
for a given input can be represented as
6
00:00:14,220 --> 00:00:17,020
a polynomial number of snapshots,
7
00:00:17,020 --> 00:00:19,630
and I'm now going to draw the snapshots only like this;
8
00:00:19,630 --> 00:00:22,310
you know that represents the input, the program,
9
00:00:22,310 --> 00:00:25,110
the read-write memory, as well.
10
00:00:25,110 --> 00:00:28,290
We've already seen that the state of the
11
00:00:28,290 --> 00:00:31,010
non deterministic RAM at each point in time
12
00:00:31,010 --> 00:00:33,900
can be represented as a snapshot
13
00:00:33,900 --> 00:00:36,420
and that snapshot
14
00:00:36,420 --> 00:00:39,060
can be represented as the Boolean formula,
15
00:00:39,060 --> 00:00:43,060
so now that we found out how we can encode a snapshot into a Boolean formula,
16
00:00:43,060 --> 00:00:45,210
let's go back to our main mission,
17
00:00:45,210 --> 00:00:47,260
showing that any problem
18
00:00:47,260 --> 00:00:49,570
that can be solved on a non deterministic RAM
19
00:00:49,570 --> 00:00:52,400
can be encoded as a SAT formula.
20
00:00:52,400 --> 00:00:55,660
And the idea of this is to build a huge--
21
00:00:55,660 --> 00:00:58,730
well, not that huge; it's all going to be polynomial size,
22
00:00:58,730 --> 00:01:00,580
but it's still going to be very large,
23
00:01:00,580 --> 00:01:04,110
so the idea is to build a very large Boolean formula
24
00:01:04,110 --> 00:01:05,220
as follows.
25
00:01:05,220 --> 00:01:07,720
each timestep of the algorithm
26
00:01:07,720 --> 00:01:10,390
is going to be represented as a snapshot.
27
00:01:10,390 --> 00:01:12,640
Then we're going to ensure that
28
00:01:12,640 --> 00:01:14,920
the first of these snapshots
29
00:01:14,920 --> 00:01:17,960
represents the memory of the RAM at
30
00:01:17,960 --> 00:01:19,220
t =0.
31
00:01:19,220 --> 00:01:22,020
What that means is that the program starts
32
00:01:22,020 --> 00:01:24,510
at the first line of execution
33
00:01:24,510 --> 00:01:27,790
and of course that memory contains the input
34
00:01:27,790 --> 00:01:30,580
that we're giving to that program or algorithm.
35
00:01:30,580 --> 00:01:33,160
Then thirdly, we have to ensure that the snapshots
36
00:01:33,160 --> 00:01:34,900
fit together.
37
00:01:34,900 --> 00:01:37,320
What I mean by that is even though it's a non deterministic RAM
38
00:01:37,320 --> 00:01:39,180
if at a certain point in time,
39
00:01:39,180 --> 00:01:41,210
say t = x,
40
00:01:41,210 --> 00:01:43,180
it is in a certain state,
41
00:01:43,180 --> 00:01:45,310
then at the next timestep,
42
00:01:45,310 --> 00:01:46,910
t at x plus 1,
43
00:01:46,910 --> 00:01:49,320
there's only a limited number of choices
44
00:01:49,320 --> 00:01:52,050
or potential states that machine can be in.
45
00:01:52,050 --> 00:01:54,890
So if we were having a deterministic RAM,
46
00:01:54,890 --> 00:01:57,160
actually as we already said,
47
00:01:57,160 --> 00:02:00,200
the state of the machine added time point x
48
00:02:00,200 --> 00:02:04,580
already clearly determines what state the machine will be in at point x plus 1.
49
00:02:04,580 --> 00:02:06,780
For a non deterministic RAM,
50
00:02:06,780 --> 00:02:09,400
if you use the if better operation
51
00:02:09,400 --> 00:02:11,940
then there can be 2 different states at the next time point.
52
00:02:11,940 --> 00:02:14,720
And then finally, we have to ensure that the Boolean formula
53
00:02:14,720 --> 00:02:17,610
that we're building has an input to SAT
54
00:02:17,610 --> 00:02:19,170
can only be satisfied
55
00:02:19,170 --> 00:02:23,060
if the algorithm returns yes at some point in time.
56
00:02:23,060 --> 00:02:26,430
Otherwise, because we have a decision problem, if the algorithm returns no,
57
00:02:26,430 --> 00:02:29,280
we do not want the Boolean formula
58
00:02:29,280 --> 99:59:59,000
to be satisfiable.
PK v#iA G Unit_2.4_-_Proof_of_SAT_(Optional)/09-Building_A_Boolean_Formula.en.srt1
00:00:00,000 --> 00:00:02,380
We already know how to do the first part of this.
2
00:00:02,380 --> 00:00:04,510
We just have to write a Boolean formula
3
00:00:04,510 --> 00:00:06,140
for each single timestep.
4
00:00:06,140 --> 00:00:08,440
The second part is also not that difficult.
5
00:00:08,440 --> 00:00:10,090
If we are given an algorithm
6
00:00:10,090 --> 00:00:13,590
and an input of that algorithm, we already know what the first snapshot
7
00:00:13,590 --> 00:00:15,560
of the RAM is going to look like.
8
00:00:15,560 --> 00:00:19,220
The program will start at the first line of the program code,
9
00:00:19,220 --> 00:00:22,390
and the memory contains nothing but the input itself,
10
00:00:22,390 --> 00:00:24,910
so given the way that the Boolean formula is written,
11
00:00:24,910 --> 00:00:28,190
all we have to ensure that we enforce the variables
12
00:00:28,190 --> 00:00:30,410
for the first snapshots
13
00:00:30,410 --> 00:00:33,380
to represent that state that we already know,
14
00:00:33,380 --> 00:00:35,720
but we can ensure that, so for example,
15
00:00:35,720 --> 00:00:39,540
if in a Boolean formula, you want a variable x1 to be set to true,
16
00:00:39,540 --> 00:00:42,710
you would write it like this; you would have certain statements of the Boolean formula,
17
00:00:42,710 --> 00:00:45,300
and then you would just put the variable x1 here,
18
00:00:45,300 --> 00:00:46,970
and then continue the formula,
19
00:00:46,970 --> 00:00:48,730
and then you know it has to be set to true,
20
00:00:48,730 --> 00:00:51,470
so in this way, you can enforce the
21
00:00:51,470 --> 00:00:54,360
Boolean formula that represents the first snapshot
22
00:00:54,360 --> 00:00:57,350
to present the memory of the RAM exactly at
23
00:00:57,350 --> 00:00:59,780
time point t equals 0.
24
00:00:59,780 --> 00:01:01,570
The fourth one here
25
00:01:01,570 --> 00:01:03,950
that the Boolean formula can only be satisfied
26
00:01:03,950 --> 00:01:05,770
if the algorithm returns yes;
27
00:01:05,770 --> 00:01:07,470
that is also not that difficult to check,
28
00:01:07,470 --> 00:01:10,480
because again using a technique like this here
29
00:01:10,480 --> 00:01:14,440
all we have to do is ensure that at a certain point in time,
30
00:01:14,440 --> 00:01:17,320
the algorithm here is at the program line
31
00:01:17,320 --> 00:01:20,960
or the RAM executes the line of the algorithm here
32
00:01:20,960 --> 00:01:23,770
or one line of the algorithm here
33
00:01:23,770 --> 00:01:26,000
that says we return yes
34
00:01:26,000 --> 00:01:29,010
so that algorithm gives us the yes value.
35
00:01:29,010 --> 00:01:32,590
So the only part that requires a little more thought is the third part here,
36
00:01:32,590 --> 99:59:59,000
how we can ensure that various snapshots fit together.
PK w#iAQ ~= = A Unit_2.4_-_Proof_of_SAT_(Optional)/10-Connecting_Snapshots.en.srt1
00:00:00,000 --> 00:00:01,940
So let's take a quick look at where we are so far.
2
00:00:01,940 --> 00:00:04,500
What I first introduced to you is the concept of
3
00:00:04,500 --> 00:00:06,660
snapshots of the RAM,
4
00:00:06,660 --> 00:00:08,470
so you can look into the machine
5
00:00:08,470 --> 00:00:12,470
at any point in time that a polynomial time algorithm executes,
6
00:00:12,470 --> 00:00:17,140
and then you see exactly what state the RAM is at that certain point in time,
7
00:00:17,140 --> 00:00:19,990
so which line of the program it's executing
8
00:00:19,990 --> 00:00:21,400
and also what's in the memory.
9
00:00:21,400 --> 00:00:24,040
I've now also shown you that we can represent
10
00:00:24,040 --> 00:00:26,940
a snapshot as a Boolean formula.
11
00:00:26,940 --> 00:00:30,390
What that means is that I've shown you how to construct a Boolean formula
12
00:00:30,390 --> 00:00:33,160
so that when you have a satisfying assignment
13
00:00:33,160 --> 00:00:35,140
for this Boolean formula and there can be many.
14
00:00:35,140 --> 00:00:39,770
Then you can reconstruct this snapshot from the satisfying assignment.
15
00:00:39,770 --> 00:00:42,660
What we also know is the assignment of the variables
16
00:00:42,660 --> 00:00:44,960
for the first Boolean formula,
17
00:00:44,960 --> 00:00:46,610
so at time point zero,
18
00:00:46,610 --> 00:00:48,170
and the reason why we know that is that
19
00:00:48,170 --> 00:00:50,460
at the beginning, we know what the machine is doing,
20
00:00:50,460 --> 00:00:52,460
because in the memory there's the input,
21
00:00:52,460 --> 00:00:54,330
the algorithm starts at the first line,
22
00:00:54,330 --> 00:00:57,550
and in the memory where we have the output, and intermediate results,
23
00:00:57,550 --> 00:00:59,190
there's nothing in there,
24
00:00:59,190 --> 00:01:02,340
so here, we already know what the variables are going to be.
25
00:01:02,340 --> 00:01:04,190
Now why are we doing all of this?
26
00:01:04,190 --> 00:01:07,300
In the end, what we want to show is if we solve SAT for this
27
00:01:07,300 --> 00:01:09,340
huge Boolean formula that we're building
28
00:01:09,340 --> 00:01:10,590
and we're not done yet,
29
00:01:10,590 --> 00:01:12,760
if we solve SAT for this formula here,
30
00:01:12,760 --> 00:01:14,920
then we want to know what the machine is actually doing
31
00:01:14,920 --> 00:01:17,410
or in other words, what we want to get is
32
00:01:17,410 --> 00:01:21,330
a protocol of what the algorithm here has done.
33
00:01:21,330 --> 00:01:23,310
So each of the Boolean formulas here
34
00:01:23,310 --> 00:01:25,310
represents a snapshot,
35
00:01:25,310 --> 00:01:27,140
but now we need to ensure that they fit together,
36
00:01:27,140 --> 00:01:29,800
because once the machine starts out in this snapshot,
37
00:01:29,800 --> 00:01:31,360
it will move to the next one,
38
00:01:31,360 --> 00:01:35,140
and so we must make sure that if we have an assignment for the variables here
39
00:01:35,140 --> 00:01:36,850
that represent a snapshot,
40
00:01:36,850 --> 00:01:40,390
then the snapshot that is represented here must fit together with one,
41
00:01:40,390 --> 00:01:43,560
so that it's kind of a valid representation of what
42
00:01:43,560 --> 00:01:45,220
the RAM is doing here.
43
00:01:45,220 --> 00:01:47,820
And the way we're going to achieve this is, of course, more Boolean formulas
44
00:01:47,820 --> 00:01:49,800
so that we add to the game,
45
00:01:49,800 --> 00:01:51,950
and to do that, I would like you to think about
46
00:01:51,950 --> 00:01:53,780
some statements for a bit
47
00:01:53,780 --> 00:01:56,580
regarding how snapshots connected to each other.
48
00:01:56,580 --> 00:01:58,540
So what I would like you to tell me is
49
00:01:58,540 --> 00:02:00,940
which of the following statements is true?
50
00:02:00,940 --> 00:02:03,000
The first one is one a deterministic RAM,
51
00:02:03,000 --> 00:02:06,630
if we know what state that machine is in a time point to,
52
00:02:06,630 --> 00:02:11,270
we can clearly state what the state will be at time t plus 1.
53
00:02:11,270 --> 00:02:13,960
The second one is I want you to tell me if
54
00:02:13,960 --> 00:02:17,630
this here were true if instead of a deterministic RAM,
55
00:02:17,630 --> 00:02:20,240
we were talking about a non deterministic RAM.
56
00:02:20,240 --> 00:02:22,620
The third one is a non deterministic RAM
57
00:02:22,620 --> 00:02:26,120
behaves exactly like a deterministic RAM
58
00:02:26,120 --> 00:02:29,240
except when we use the ifbetter function,
59
00:02:29,240 --> 00:02:31,120
and finally, if we use the ifbetter function,
60
00:02:31,120 --> 00:02:34,260
there can be any number of next states,
61
00:02:34,260 --> 00:02:36,570
so not 1, not 2, not 3, but
62
00:02:36,570 --> 00:02:38,470
basically an arbitrarily large number of states,
63
00:02:38,470 --> 00:02:40,760
and we can not make any statement about that.
64
00:02:40,760 --> 00:02:42,550
So which of the following is true?
65
00:02:42,550 --> 99:59:59,000
Please check all of the boxes where the statements are true.
PK x#iAh!` J Unit_2.4_-_Proof_of_SAT_(Optional)/11-Connecting_Snapshots_Solution.en.srt1
00:00:00,000 --> 00:00:03,050
So the first statement is clearly true, and we talked about this a couple of times
2
00:00:03,050 --> 00:00:04,400
in this unit.
3
00:00:04,400 --> 00:00:06,350
If you know the state of the deterministic RAM,
4
00:00:06,350 --> 00:00:08,320
that means you know whats in the memory
5
00:00:08,320 --> 00:00:11,160
and where the program is currently executing,
6
00:00:11,160 --> 00:00:14,500
then you can easily tell what the machine will do as a next step.
7
00:00:14,500 --> 00:00:16,230
The second one is of course not true,
8
00:00:16,230 --> 00:00:18,040
because we have the if-better function, and so
9
00:00:18,040 --> 00:00:21,810
if we know the state of a non deterministic RAM at time point t,
10
00:00:21,810 --> 00:00:24,780
and at that point in time, we call the if-better function,
11
00:00:24,780 --> 00:00:27,110
then we can not say what the state will be
12
00:00:27,110 --> 00:00:28,410
at time t plus 1.
13
00:00:28,410 --> 00:00:31,820
There are basically either the first part of the code is executed
14
00:00:31,820 --> 00:00:34,260
or the second part of the code is executed.
15
00:00:34,260 --> 00:00:36,480
And this gives us the answer for
16
00:00:36,480 --> 00:00:38,230
the last 3 statements here,
17
00:00:38,230 --> 00:00:40,510
so this one here is false, because a non deterministic RAM
18
00:00:40,510 --> 00:00:42,470
does not behave like a deterministic RAM,
19
00:00:42,470 --> 00:00:44,940
but there is actually only one case where it does this,
20
00:00:44,940 --> 00:00:47,220
and that is when if-better is called,
21
00:00:47,220 --> 00:00:49,220
so this statement here is true,
22
00:00:49,220 --> 00:00:52,690
and when the if-better is called, there can not be any number of next states.
23
00:00:52,690 --> 00:00:54,240
There can only be 2,
24
00:00:54,240 --> 00:00:57,140
because you'll remember, the if-better function works as follows.
25
00:00:57,140 --> 00:01:00,090
You call if-better, then there's some code here,
26
00:01:00,090 --> 00:01:02,620
and then you have an else statement, and there's some code here.
27
00:01:02,620 --> 00:01:04,269
Then there's only 2 possibilities,
28
00:01:04,269 --> 00:01:06,060
so it's not any number of states;
29
00:01:06,060 --> 00:01:08,420
it is actually just 2,
30
00:01:08,420 --> 99:59:59,000
so this is also false.
PK y#iAa%^_ _ 2 Unit_2.4_-_Proof_of_SAT_(Optional)/12-Rules.en.srt1
00:00:00,000 --> 00:00:02,009
Now we are almost there.
2
00:00:02,009 --> 00:00:05,380
What I would like you to do now is think about
3
00:00:05,380 --> 00:00:08,380
when you analyze an algorithm using pen and paper,
4
00:00:08,380 --> 00:00:10,030
how would you go about that?
5
00:00:10,030 --> 00:00:13,120
What you basically say is every program here and your variables here,
6
00:00:13,120 --> 00:00:15,400
so how do you get from here to here?
7
00:00:15,400 --> 00:00:18,430
So basically, it's a number of rules that look like this.
8
00:00:18,430 --> 00:00:22,100
If we are at a certain line of the code,
9
00:00:22,100 --> 00:00:25,270
so say we are here, and usually that line of code will
10
00:00:25,270 --> 00:00:27,810
also use some variables, but it doesn't have to,
11
00:00:27,810 --> 00:00:29,510
but usually it will of course,
12
00:00:29,510 --> 00:00:32,500
so certain variables are set to a given value.
13
00:00:32,500 --> 00:00:35,030
Then we know what the program is going to do next.
14
00:00:35,030 --> 00:00:37,620
For example, it's going to jump to the next line of code,
15
00:00:37,620 --> 00:00:40,150
and it's going to modify this variable here.
16
00:00:40,150 --> 00:00:42,160
So how many of these rules are there?
17
00:00:42,160 --> 00:00:43,690
Well, for a single line of code,
18
00:00:43,690 --> 00:00:45,830
it depends on the variables here,
19
00:00:45,830 --> 00:00:49,370
and let's assume that one line of code uses a maximum of 3 variables.
20
00:00:49,370 --> 00:00:52,310
If you were to count how many of the rules there are,
21
00:00:52,310 --> 00:00:56,390
it's the number of different values that one variable can take
22
00:00:56,390 --> 00:00:59,710
times the number of different values that the second variable can take
23
00:00:59,710 --> 00:01:02,810
times the number of values that the third variable can take.
24
00:01:02,810 --> 00:01:04,750
So for one line of code,
25
00:01:04,750 --> 00:01:08,420
that's actually just O of 1 as the constant.
26
00:01:08,420 --> 00:01:09,410
Why is that?
27
00:01:09,410 --> 00:01:13,340
Well, because we set that on the RAM variables can not get arbitrarily large,
28
00:01:13,340 --> 00:01:16,100
so there's only a constant number
29
00:01:16,100 --> 00:01:18,350
of different values that a variable can take,
30
00:01:18,350 --> 00:01:21,450
so even if we have 3 different variables
31
00:01:21,450 --> 00:01:23,440
and consider all of the combinations,
32
00:01:23,440 --> 00:01:25,410
it will be a huge number usually,
33
00:01:25,410 --> 00:01:27,310
but it will be a constant number
34
00:01:27,310 --> 00:01:28,750
for one line of code.
35
00:01:28,750 --> 00:01:30,440
Now if we're not looking at one line of code
36
00:01:30,440 --> 00:01:32,510
but all lines of code,
37
00:01:32,510 --> 00:01:34,510
then this actually doesn't change,
38
00:01:34,510 --> 00:01:38,940
because we have a constant number of possibilities for each line in the code
39
00:01:38,940 --> 00:01:42,380
and the program has constant size just as before.
40
00:01:42,380 --> 00:01:46,080
So there's a constant number of rules
41
00:01:46,080 --> 00:01:48,560
that will tell us exactly what the machine is going to do
42
00:01:48,560 --> 00:01:50,130
in the deterministic case.
43
00:01:50,130 --> 00:01:53,060
We're going to go to the non deterministic case in a minute,
44
00:01:53,060 --> 99:59:59,000
because there of course, as we just found out, the if-then rules don't work.
PK y#iAPLj& & 5 Unit_2.4_-_Proof_of_SAT_(Optional)/13-Behavior.en.srt1
00:00:00,000 --> 00:00:03,590
So how the machine behaves is a large collection
2
00:00:03,590 --> 00:00:07,650
of rules that look like if the variables are set in a certain way,
3
00:00:07,650 --> 00:00:10,200
then this is what happens next.
4
00:00:10,200 --> 00:00:14,130
Now the question is can we use a Boolean formula to express an if-then statement?
5
00:00:14,130 --> 00:00:17,110
And I will actually let you figure that out in our next quiz.
6
00:00:17,110 --> 00:00:19,460
So I'm going to give you the following Boolean formula,
7
00:00:19,460 --> 00:00:22,570
x1 and x2 and x3.
8
00:00:22,570 --> 00:00:25,280
We're going to do a big not over this
9
00:00:25,280 --> 00:00:31,960
or x4 and x5 and x6.
10
00:00:31,960 --> 00:00:35,270
And I'm going to give you 4 cases now to look at,
11
00:00:35,270 --> 00:00:39,320
so we're going to look at this part here and this part here,
12
00:00:39,320 --> 00:00:42,510
and I'm not including this big not here,
13
00:00:42,510 --> 00:00:46,620
so I'm just looking at how x1, x2, and x3 evaluates;
14
00:00:46,620 --> 00:00:49,240
the not is not included.
15
00:00:49,240 --> 00:00:51,840
So there are 2 possibilities of course.
16
00:00:51,840 --> 00:00:56,000
It can be either true, or it can be false,
17
00:00:56,000 --> 00:00:58,780
and those variables over here, completely independent over here,
18
00:00:58,780 --> 00:01:01,330
they can of course also be true and false,
19
00:01:01,330 --> 00:01:04,970
so overall, we have 4 different cases,
20
00:01:04,970 --> 00:01:07,330
and what I would like you to quickly tell me is
21
00:01:07,330 --> 00:01:09,840
in which of these 4 cases here,
22
00:01:09,840 --> 99:59:59,000
the whole Boolean formula is satisfied.
PK {#iAͣLd > Unit_2.4_-_Proof_of_SAT_(Optional)/14-Behavior_Solution.en.srt1
00:00:00,000 --> 00:00:03,250
So the Boolean formula here is almost always satisfied.
2
00:00:03,250 --> 00:00:06,140
It's satisfied in this case over here.
3
00:00:06,140 --> 00:00:08,740
It's satisfied in this case over here and this one.
4
00:00:08,740 --> 00:00:10,610
The only one where it's not satisfied is this one here,
5
00:00:10,610 --> 00:00:12,550
and of course that's easy to evaluate,
6
00:00:12,550 --> 00:00:17,000
so if x1 and x2 and x3 evaluates to true,
7
00:00:17,000 --> 00:00:20,120
then we have the big not, which will make it go to 0
8
00:00:20,120 --> 00:00:23,470
and 0 or 1 is equal to 1,
9
00:00:23,470 --> 00:00:27,690
so the Boolean formula is satisfied, but 0 or 0
10
00:00:27,690 --> 00:00:30,690
evaluates to 0,
11
00:00:30,690 --> 00:00:32,520
so here the Boolean formula is not satisfied.
12
00:00:32,520 --> 00:00:35,330
For these 2 cases, the Boolean formula is simply satisfied,
13
00:00:35,330 --> 00:00:38,480
because if this goes to 0, then we have the big not over here,
14
00:00:38,480 --> 00:00:42,060
so it will go to 1 and 1 over 1,
15
00:00:42,060 --> 00:00:46,220
and 1 or 0 that also evaluates to 1.
16
00:00:46,220 --> 00:00:48,540
What is this have to do with an if-then?
17
00:00:48,540 --> 00:00:50,150
Well, it's actually quite simple.
18
00:00:50,150 --> 00:00:54,200
If this part here, x1 and x2 and x3
19
00:00:54,200 --> 00:00:56,210
evaluates to 1,
20
00:00:56,210 --> 00:00:58,420
then this part over here
21
00:00:58,420 --> 00:01:02,360
must also be 1 in order to satisfied the Boolean formula.
22
00:01:02,360 --> 00:01:05,129
It does not work if this part over here is 0.
23
00:01:05,129 --> 00:01:09,500
In the other case where x1 and x2 and x3 evaluates to 0,
24
00:01:09,500 --> 00:01:12,210
then as you can see, we basically don't care
25
00:01:12,210 --> 00:01:15,950
what the other variables are doing, because the Boolean formula is already satisfied,
26
00:01:15,950 --> 00:01:18,950
and that is exactly how an if-then behaves.
27
00:01:18,950 --> 00:01:20,520
If the condition is satisfied,
28
00:01:20,520 --> 00:01:23,190
then we want something specific to happen.
29
00:01:23,190 --> 00:01:26,550
If the conditions are not satisfied, we don't really care what happens,
30
00:01:26,550 --> 99:59:59,000
or at least we're not really going to force anything to happen.
PK {#iAK-{ { ; Unit_2.4_-_Proof_of_SAT_(Optional)/15-If_Better_Step.en.srt1
00:00:00,000 --> 00:00:03,550
So finally, what about non determinism?
2
00:00:03,550 --> 00:00:07,130
What if we're using the if-better function at a certain line in the code?
3
00:00:07,130 --> 00:00:10,370
Well, then the rules here are actually much simpler
4
00:00:10,370 --> 00:00:12,200
than for a normal line of code,
5
00:00:12,200 --> 00:00:14,590
because any time we use the if-better,
6
00:00:14,590 --> 00:00:17,040
our rule is going to be
7
00:00:17,040 --> 00:00:20,950
that the program either goes to 1 line of code
8
00:00:20,950 --> 00:00:22,380
or another one,
9
00:00:22,380 --> 00:00:24,010
because that's all the if-better does.
10
00:00:24,010 --> 00:00:27,450
The if-better does not modify any variables, it doesn't depend on any variables.
11
00:00:27,450 --> 00:00:31,210
It just goes to either one line of code or the other one.
12
00:00:31,210 --> 00:00:34,230
So this is a very simple rule that we can use to say
13
00:00:34,230 --> 00:00:38,110
what will happen if the program at time point t
14
00:00:38,110 --> 99:59:59,000
point to an if-better.
PK |#iAOZ# # D Unit_2.4_-_Proof_of_SAT_(Optional)/16-Putting_It_All_Together.en.srt1
00:00:00,000 --> 00:00:02,610
So now it's time for us to put all of our building blocks together
2
00:00:02,610 --> 00:00:05,790
and we're just this close to showing that
3
00:00:05,790 --> 00:00:08,820
SAT is indeed NP complete.
4
00:00:08,820 --> 00:00:11,180
So we started out with a problem in NP
5
00:00:11,180 --> 00:00:16,040
and input fallout problem; of course, this here can be any problem in NP
6
00:00:16,040 --> 00:00:18,780
and this here can be any input fallout problem
7
00:00:18,780 --> 00:00:19,640
and what do we then do?
8
00:00:19,640 --> 00:00:21,440
We said if the problem is in NP,
9
00:00:21,440 --> 00:00:24,110
then there must be some algorithm for that problem
10
00:00:24,110 --> 00:00:26,780
which runs in polynomial time on a non deterministic RAM,
11
00:00:26,780 --> 00:00:28,530
so an algorithm or a program
12
00:00:28,530 --> 00:00:30,530
you can call it any way you want,
13
00:00:30,530 --> 00:00:32,280
so that will run in polynomial time,
14
00:00:32,280 --> 00:00:34,790
and the algorithm at some lines of the code
15
00:00:34,790 --> 00:00:37,260
either says yes or says no,
16
00:00:37,260 --> 00:00:40,520
but it's running in polynomial time in any case,
17
00:00:40,520 --> 00:00:42,200
and of course the input for the problem,
18
00:00:42,200 --> 00:00:44,320
well that is basically just the number of variables
19
00:00:44,320 --> 00:00:47,160
in the memory of the machine as it starts out.
20
00:00:47,160 --> 00:00:50,190
Then we took all this and of course it's a huge Boolean formula
21
00:00:50,190 --> 00:00:53,120
and you would probably never really want to write it out explicitly,
22
00:00:53,120 --> 00:00:57,280
but it exists and it contains a number of components that we have discussed.
23
00:00:57,280 --> 00:01:00,620
So one part of the Boolean formula encodes snapshots
24
00:01:00,620 --> 00:01:03,340
of the algorithm as it runs on the machine.
25
00:01:03,340 --> 00:01:06,180
Then we said we have to have 1 part that ensures that
26
00:01:06,180 --> 00:01:09,930
the first snapshot properly represents the starting conditions
27
00:01:09,930 --> 00:01:13,090
so that it properly the algorithm starting at line one
28
00:01:13,090 --> 00:01:16,110
and also the memory representing the input for the problem.
29
00:01:16,110 --> 00:01:18,150
Then what we just discussed is that
30
00:01:18,150 --> 00:01:21,330
through a number of rules that look like if-then,
31
00:01:21,330 --> 00:01:25,070
you can ensure that the snapshot is at a certain point in time t
32
00:01:25,070 --> 00:01:28,290
and at the following time point fit together,
33
00:01:28,290 --> 00:01:30,330
and then finally,
34
00:01:30,330 --> 00:01:32,440
since this here is a decision problem,
35
00:01:32,440 --> 00:01:34,960
we want to ensure that the Boolean formula
36
00:01:34,960 --> 00:01:36,960
can only be satisfied
37
00:01:36,960 --> 00:01:38,650
if at certain point in time
38
00:01:38,650 --> 00:01:40,660
the algorithm returns yes,
39
00:01:40,660 --> 00:01:43,980
so this is the last part we have to add to the Boolean formula,
40
00:01:43,980 --> 00:01:45,690
and this is actually quite easy to ensure,
41
00:01:45,690 --> 00:01:48,540
because once the algorithm reaches this line of the code,
42
00:01:48,540 --> 00:01:51,440
wherever it may be, and you can even have multiple lines
43
00:01:51,440 --> 00:01:53,020
where the algorithm returns yes,
44
00:01:53,020 --> 00:01:55,340
but once such line has been reached,
45
00:01:55,340 --> 00:01:57,420
the algorithm returns yes and stops,
46
00:01:57,420 --> 00:02:00,260
so this her is very easy to ensure.
47
00:02:00,260 --> 00:02:02,900
You just have to make sure that there's one snapshot
48
00:02:02,900 --> 00:02:06,120
where the algorithm is in a line that returns a yes.
49
00:02:06,120 --> 00:02:08,449
So once we have constructed this Boolean formula,
50
00:02:08,449 --> 00:02:11,650
what happens if we solve SAT for this formula?
51
00:02:11,650 --> 00:02:13,450
Then there's 2 cases that can happen,
52
00:02:13,450 --> 00:02:15,120
because SAT is also a decision problem,
53
00:02:15,120 --> 00:02:18,400
so either SAT returns yes
54
00:02:18,400 --> 00:02:20,170
or it returns no.
55
00:02:20,170 --> 00:02:22,240
What if it returns yes?
56
00:02:22,240 --> 00:02:26,020
If it returns yes, that means that there is a satisfying assignment
57
00:02:26,020 --> 00:02:29,090
for this Boolean formula, and a satisfying assignment
58
00:02:29,090 --> 00:02:30,350
will have the following property.
59
00:02:30,350 --> 00:02:33,610
First of all, it will encode valid snapshots
60
00:02:33,610 --> 00:02:35,240
of where the algorithm is
61
00:02:35,240 --> 00:02:36,810
and whats in the memory.
62
00:02:36,810 --> 00:02:39,920
Secondly, it will also ensure that the machine starts out
63
00:02:39,920 --> 00:02:41,040
in the right place,
64
00:02:41,040 --> 00:02:43,090
meaning it starts out at line 1 of the code
65
00:02:43,090 --> 00:02:45,530
and representing the input for the problem,
66
00:02:45,530 --> 00:02:47,740
it will ensure that all the snapshots
67
00:02:47,740 --> 00:02:49,820
that it has figured out will fit together
68
00:02:49,820 --> 00:02:52,070
and it can only return yes
69
00:02:52,070 --> 00:02:55,130
if the algorithm returns yes at some point in time.
70
00:02:55,130 --> 00:02:57,060
So if we have a yes here,
71
00:02:57,060 --> 00:03:00,740
we also know that this problem or the decision problem here
72
00:03:00,740 --> 00:03:04,380
is one where a non deterministic RAM would also answer yes.
73
00:03:04,380 --> 00:03:06,230
If it says no, on the other hand,
74
00:03:06,230 --> 00:03:08,080
what does that mean?
75
00:03:08,080 --> 00:03:12,340
Well, we know that we always can encode the snapshots,
76
00:03:12,340 --> 00:03:16,060
so it's not going to say no, because it can not encode a snapshot,
77
00:03:16,060 --> 00:03:18,240
because that's possible always.
78
00:03:18,240 --> 00:03:21,670
It also won't say no due to this property here,
79
00:03:21,670 --> 00:03:24,590
because well, we have ensured
80
00:03:24,590 --> 00:03:26,210
that the snapshot can properly encoded,
81
00:03:26,210 --> 00:03:30,060
so there's no mistake in the formula here, so it can not say no because of this here.
82
00:03:30,060 --> 00:03:32,240
It also can not say no because of this here,
83
00:03:32,240 --> 00:03:34,280
because the machine will always run
84
00:03:34,280 --> 00:03:36,090
and you can make the snapshots fit together.
85
00:03:36,090 --> 00:03:40,560
The only reason why there can be no satisfying assignment
86
00:03:40,560 --> 00:03:45,100
is if the algorithm does not return yes at a certain point in time
87
00:03:45,100 --> 00:03:49,370
and since this algorithm solve this problem here,
88
00:03:49,370 --> 00:03:51,220
if it can not reach yes,
89
00:03:51,220 --> 00:03:53,770
then this means that this decision problem here
90
00:03:53,770 --> 00:03:55,730
is also a no.
91
00:03:55,730 --> 00:03:57,910
So satisfiability
92
00:03:57,910 --> 00:04:00,600
only if this problem given this input here
93
00:04:00,600 --> 00:04:02,540
is a yes.
94
00:04:02,540 --> 00:04:04,470
So now that we have put it together,
95
00:04:04,470 --> 00:04:08,030
here's our final quiz for proving that SAT is NP complete,
96
00:04:08,030 --> 00:04:11,000
and what I would like you to do is to recap
97
00:04:11,000 --> 00:04:13,550
the properties of this Boolean formula here.
98
00:04:13,550 --> 00:04:15,680
First of all, what is the size of this Boolean formula
99
00:04:15,680 --> 00:04:18,660
for an input of size n
100
00:04:18,660 --> 00:04:20,820
and remember this algorithm here
101
00:04:20,820 --> 00:04:22,420
runs in polynomial time.
102
00:04:22,420 --> 00:04:25,830
So is this Boolean formula up here
103
00:04:25,830 --> 00:04:27,160
constant in size,
104
00:04:27,160 --> 00:04:30,230
polynomial in size, or exponential in size
105
00:04:30,230 --> 00:04:32,330
with respect to n?
106
00:04:32,330 --> 00:04:35,460
and then can this Boolean formula encode
107
00:04:35,460 --> 00:04:39,220
any algorithm at least for a problem that is an NP?
108
00:04:39,220 --> 00:04:43,440
Can it encode any input of size n that were given to that problem?
109
00:04:43,440 --> 00:04:46,440
Finally is this Boolean formula satisfiable if
110
00:04:46,440 --> 00:04:49,470
the input here is a yes
111
00:04:49,470 --> 00:04:51,480
to not decision problem here
112
00:04:51,480 --> 00:04:53,310
or are there any other cases where
113
00:04:53,310 --> 00:04:55,190
we could also have satisfiabilty.
114
00:04:55,190 --> 99:59:59,000
So please check all of these that are true.
PK }#iA` M Unit_2.4_-_Proof_of_SAT_(Optional)/17-Putting_It_All_Together_Solution.en.srt1
00:00:00,000 --> 00:00:02,720
And of course, once you've gone through the proof,
2
00:00:02,720 --> 00:00:05,720
this was a rather easy quiz just for relaxation
3
00:00:05,720 --> 00:00:08,930
after all of these Boolean formulas and satisfiabilities.
4
00:00:08,930 --> 00:00:12,060
So of course, this formula has polynomial size,
5
00:00:12,060 --> 00:00:14,300
because when you constructed it,
6
00:00:14,300 --> 00:00:15,690
we took care of that.
7
00:00:15,690 --> 00:00:17,230
It can encode any algorithm.
8
00:00:17,230 --> 00:00:21,370
We did not make any special assumptions or restrictions on this algorithm here.
9
00:00:21,370 --> 00:00:25,040
It can also encode any input, because that basically just means
10
00:00:25,040 --> 00:00:29,110
whatever we're given, we encode it into memory and we know we can do that,
11
00:00:29,110 --> 00:00:32,350
and finally, of course, that was the purpose of the construction,
12
00:00:32,350 --> 00:00:35,600
this Boolean formula up here is only satisfiable
13
00:00:35,600 --> 00:00:40,310
if solving this problem for this input returns a yes;
14
00:00:40,310 --> 00:00:43,840
otherwise, if it's a no, you can not satisfy this formula.
15
00:00:43,840 --> 00:00:46,570
And this of course is the whole purpose of the construction,
16
00:00:46,570 --> 00:00:49,090
because what we have now shown is
17
00:00:49,090 --> 00:00:52,600
that solving SAT on this Boolean formula
18
00:00:52,600 --> 00:00:56,990
is the same as solving this problem
19
00:00:56,990 --> 00:00:59,960
for this input here,
20
00:00:59,960 --> 00:01:02,390
and what that means, of course also is
21
00:01:02,390 --> 00:01:06,130
if you can solve SAT on this Boolean formula here
22
00:01:06,130 --> 00:01:08,280
in polynomial time,
23
00:01:08,280 --> 00:01:11,460
then you have a polynomial time simulation of this algorithm here
24
00:01:11,460 --> 99:59:59,000
running on this input.
PK }#iA@
, <