1 00:00:00,012 --> 00:00:05,276 In these next three videos I want to highlight for you an unusual local search 2 00:00:05,276 --> 00:00:08,855 algorithm. It's unusual in that it's guarnetted to 3 00:00:08,855 --> 00:00:13,342 solve a non trivial and interesting problem in polynomial time. 4 00:00:13,342 --> 00:00:18,865 That problem is the two set problem which also furnishes an example of how local 5 00:00:18,865 --> 00:00:23,401 search can be applied. To constraint satisfaction problems. 6 00:00:23,401 --> 00:00:28,793 We've now mentioned 2-SAT in passing a number of times but let me just give you 7 00:00:28,793 --> 00:00:33,099 a very precise definition of the computational problem here. 8 00:00:33,099 --> 00:00:37,867 The input is a set of invariables x1 through xn at a set of m-closets. 9 00:00:37,867 --> 00:00:42,454 Each of variables is boolean. That is, you're allowed to set it to 10 00:00:42,454 --> 00:00:46,835 either true or to false. Each of the m-closets is a disjunction 11 00:00:46,835 --> 00:00:51,663 that is a Or of 2 literals. Literals is simply either a variable or 12 00:00:51,663 --> 00:00:56,661 indication of that variable. Here is an example to make this clear. 13 00:00:56,661 --> 00:00:59,791 The example has 4 variables and 4 clauses. 14 00:00:59,791 --> 00:01:04,615 The variables are X1 through X4. So, the first clause is X1 or X2. 15 00:01:04,615 --> 00:01:08,592 So, its standard use is V symbol to denote logical OR. 16 00:01:08,592 --> 00:01:14,188 So, what this clause means is that its satisfied if either X1 is true or if X2 17 00:01:14,188 --> 00:01:18,011 is true. The only way you can screw up satisfying 18 00:01:18,011 --> 00:01:21,905 this clause is by setting both X1 and and X2 to false. 19 00:01:21,905 --> 00:01:24,977 The next clause has the form not-X1 or X3. 20 00:01:24,977 --> 00:01:30,714 The only way you can screw up satisfying this clause is by setting X1 to be true 21 00:01:30,714 --> 00:01:34,689 and X3 to be false. Then we're going to have a clause x3 or 22 00:01:34,689 --> 00:01:37,747 x4. Again this is satisfied unless you wind 23 00:01:37,747 --> 00:01:43,133 up setting x3 and x4 both to be false. And then finally we have a clause not x2 24 00:01:43,133 --> 00:01:46,656 or not x4. And this is satisfied except in the case 25 00:01:46,656 --> 00:01:49,562 that you assign both x2 and x4 to be true. 26 00:01:49,562 --> 00:01:54,802 Because we're interested in whether all of the clauses can be simultaneously 27 00:01:54,802 --> 00:01:59,358 satisfied, one often joins the clauses using logical and symbols. 28 00:01:59,358 --> 00:02:04,557 That's what this upside down V denotes. So that's would a 2-SAT instance looks 29 00:02:04,557 --> 00:02:09,692 like and then we're just interested in a decision problem given such an instance, 30 00:02:09,692 --> 00:02:14,037 we just want to know Is it or Is it not possible to assign values to the 31 00:02:14,037 --> 00:02:18,177 invariables, True or False. So that every single one of the M clauses 32 00:02:18,177 --> 00:02:21,142 is satisfied. The two set instance that I gave you as 33 00:02:21,142 --> 00:02:25,537 an example is indeed satisfiable. There's actually more than 1 satisfying 34 00:02:25,537 --> 00:02:28,412 assignment but here's a way to produce one of them. 35 00:02:28,412 --> 00:02:32,802 Let's start with the first clause, to satisfy either X1 or X2 it needs to be 36 00:02:32,802 --> 00:02:33,798 set. to true. 37 00:02:33,798 --> 00:02:37,965 Let's go ahead and set x1 to be true. That takes care of the first clause. 38 00:02:37,965 --> 00:02:42,459 Now we look at the second clause and we notice, oops, if we set x1 to be true the 39 00:02:42,459 --> 00:02:46,387 only way we can satisfy the second clause is by setting x3 to be true. 40 00:02:46,387 --> 00:02:48,338 Let's do that. X1 and x3 are true. 41 00:02:48,338 --> 00:02:52,592 X2 and x4 we haven't assigned. Now, by assigning X3 to be true we knock 42 00:02:52,592 --> 00:02:56,192 off not just that 2nd clause, we also satisfy the 3rd clause. 43 00:02:56,192 --> 00:03:00,607 So that leaves us with the 4th clause, and now we just got to make sure we set 44 00:03:00,607 --> 00:03:04,542 either X2 or X4 to be false. Let's just go ahead and set them both to 45 00:03:04,542 --> 00:03:07,402 be false. That satisfies all of the clauses. 46 00:03:07,402 --> 00:03:12,059 Much is known where the competition tractability, or as the case may be 47 00:03:12,059 --> 00:03:15,713 intractability of contraints satisfaction problems. 48 00:03:15,713 --> 00:03:20,785 2-SAT is not exceptional in that sense we know all kinds of things about it. 49 00:03:20,785 --> 00:03:25,242 It is, it is exceptional in that it is polynomial time [UNKNOWN]. 50 00:03:25,242 --> 00:03:29,607 There are many ways of proving this fact. Alumni of part one may already be 51 00:03:29,607 --> 00:03:34,402 familiar with one really nice way, which to reduce the 2-SAT problem to computing 52 00:03:34,402 --> 00:03:38,382 of the strongly connected components of a suitable directed graph. 53 00:03:38,382 --> 00:03:42,982 That reduction in fact shows that the 2-SAT problem can be solved in linear 54 00:03:42,982 --> 00:03:45,327 Time. Another way you can establish its 55 00:03:45,327 --> 00:03:49,542 computational tractability is using a type of backtracking algorithm. 56 00:03:49,542 --> 00:03:54,167 And by backtracking here I mean something sort of similar to what we did when we 57 00:03:54,167 --> 00:03:58,497 gave our faster exponential time algorithm for the vertex cover problem, 58 00:03:58,497 --> 00:04:02,882 for instances which have small vertex cover, small optimal solution. 59 00:04:02,882 --> 00:04:06,495 Both of these proofs of computational tractability are non-trivial. 60 00:04:06,495 --> 00:04:10,404 I'm not going to discuss the mirror because instead I want to spend our time 61 00:04:10,404 --> 00:04:13,497 on a local search algorithm. Roughly speaking, the way the 62 00:04:13,497 --> 00:04:17,691 back-tracking algorithm works in a 2 set instance is you start by looking at some 63 00:04:17,691 --> 00:04:21,773 variable, let's say variable X1. And, as a tentative working hypothesis, 64 00:04:21,773 --> 00:04:25,643 you assign x1 the value of, true. Now, through the clauses, setting x1 to 65 00:04:25,643 --> 00:04:29,862 be true, has ramifications for what other variables, have to necessarily be, if 66 00:04:29,862 --> 00:04:32,146 you're going to have a satisfying assignment. 67 00:04:32,146 --> 00:04:36,031 So you go ahead and propogate those implications, to the rest of the The 68 00:04:36,031 --> 00:04:38,393 variables. If you reach a contradiction, if there's 69 00:04:38,393 --> 00:04:41,767 one clause demanding that x7 is set to true and a different clause demanding 70 00:04:41,767 --> 00:04:44,350 that x7 is set to false. You know that it didn't work out. 71 00:04:44,350 --> 00:04:46,858 X1 is not going to be true in any satisfying assignment. 72 00:04:46,858 --> 00:04:49,537 So you back track and you try again, setting it to be false. 73 00:04:49,537 --> 00:04:52,860 And seeing if that works out. If on the other hand you're able to 74 00:04:52,860 --> 00:04:56,800 consistently propagate all of these implications from X1 being equal to true 75 00:04:56,800 --> 00:05:00,983 to other variables, then you can just try to extend that satisfying assignment by 76 00:05:00,983 --> 00:05:04,886 walking up to a different variable and setting that tentatively to be, say, 77 00:05:04,886 --> 00:05:07,295 true. It's possible to organize this search so 78 00:05:07,295 --> 00:05:10,980 that you can correctly determine whether or not a 2-SAT instance has the 79 00:05:10,980 --> 00:05:14,864 satisfying assignment in polynomial time. Again, a non-trivial exercise. 80 00:05:14,864 --> 00:05:17,614 If you're interested, think through the Details. 81 00:05:17,614 --> 00:05:21,942 We're going to instead focus on a very cool, randomized local search algorithm, 82 00:05:21,942 --> 00:05:24,990 that again, solves 2 side instances in polynomial time. 83 00:05:24,990 --> 00:05:29,368 I don't want to give you the wrong idea, as we discussed earlier, generally local 84 00:05:29,368 --> 00:05:32,829 search heuristics are not guaranteed to run in polynomial time. 85 00:05:32,829 --> 00:05:36,626 As we said, that's true even in the weighted version of the maximum cut 86 00:05:36,626 --> 00:05:39,774 problem. This 2-SAT example is the rare case where 87 00:05:39,774 --> 00:05:44,179 we can prove it's guaranteed to converge with a correct answer quickly. 88 00:05:44,179 --> 00:05:48,738 You can use local search not merely to identify computationally tractable 89 00:05:48,738 --> 00:05:53,780 versions of satisfiability, but also to improve over naive brute force search for 90 00:05:53,780 --> 00:05:58,767 NP complete versions of satisfiability. In particular, let's talk about the 3-sat 91 00:05:58,767 --> 00:06:01,309 problem. So 3-sat, no surprise, is the same as 92 00:06:01,309 --> 00:06:04,913 2-SAT, except the clauses involve three literals rather than two. 93 00:06:04,913 --> 00:06:09,114 So while a clause in a 2-SAT instance can be thought of as forbidding one of the 94 00:06:09,114 --> 00:06:13,147 four possible joint assignments of a pair of variables, a clause in a 3-sat 95 00:06:13,147 --> 00:06:17,391 instance can be thought of as forbidding one of the eight possible joint values 96 00:06:17,391 --> 00:06:21,649 for a triple variable. Bumping up the clause length from 2 or 3 97 00:06:21,649 --> 00:06:27,153 changes the problem from computationally tractable to computationally intractable. 98 00:06:27,153 --> 00:06:31,333 Indeed 3-SAT is in some sense the canonical NP-complete problem. 99 00:06:31,333 --> 00:06:35,922 You'll often see the Cook Levin theorem stated as 3-SAT NP-complete. 100 00:06:35,922 --> 00:06:40,427 But just because this MP complete doesn't automatically mean, we take them with any 101 00:06:40,427 --> 00:06:44,546 interesting algorithms.So Brude-force search would just try every possible 102 00:06:44,546 --> 00:06:48,490 assignment to the variables, that's going to take time roughly 2 2^n. 103 00:06:48,490 --> 00:06:53,877 Remarkably randomized local search lets you improve dramatically over the running 104 00:06:53,877 --> 00:06:58,716 time of naive brute force search. Rather than a running time of roughly 2^n 105 00:06:58,716 --> 00:07:03,314 a very clever twist on the 2-SAT algorithm that we're about to discuss, 106 00:07:03,314 --> 00:07:07,649 which was in polynomial time. A twist on that for 3-SAT runs in time 107 00:07:07,649 --> 00:07:11,192 roughly 4/3. Raised to the N, way better than 2^N. 108 00:07:11,192 --> 00:07:16,317 This is a relatively recent result, only about a decade old due to Schoning. 109 00:07:16,317 --> 00:07:21,017 I want to focus here on how to use randomized local search to solve 2-SAT 110 00:07:21,017 --> 00:07:25,167 and polynomial time. The improvement over brute force search 111 00:07:25,167 --> 00:07:28,092 for 3-SAT will have to wait until another. 112 00:07:28,092 --> 00:07:31,198 Another day. This algorithm is due to Papi Dimitru 113 00:07:31,198 --> 00:07:36,043 from a little over 20 years ago, and the very elegant pseudocode is as follows. 114 00:07:36,043 --> 00:07:40,702 So the algorithm has 2 loops, but the outer loop's responsibility is just to 115 00:07:40,702 --> 00:07:45,522 run the budget independent random trials. For those of you who are an alumni of 116 00:07:45,522 --> 00:07:49,766 part 1, let me make an analogy with Cargill's randomized contraction 117 00:07:49,766 --> 00:07:53,033 algorithm. So for that minimum cut algorithm, we had 118 00:07:53,033 --> 00:07:57,551 our basic randomized algorithm And then we ran it a bunch of times, a bunch of 119 00:07:57,551 --> 00:08:01,411 independent trials, hoping that 1 of the independent trials would find us the 120 00:08:01,411 --> 00:08:03,846 minimum cut. Same things going to be going on here, 121 00:08:03,846 --> 00:08:06,173 the meat of the algorithm is in the inner loop. 122 00:08:06,173 --> 00:08:10,008 That has some probability of finding a satisfying assignment and then we just 123 00:08:10,008 --> 00:08:13,756 run that basic subroutine a bunch of times, hoping that 1 of the trials will 124 00:08:13,756 --> 00:08:17,681 find us a satisfying assignment. So conceptually you should just focus on 125 00:08:17,681 --> 00:08:21,746 a fixed iteration of this outer 4 loop. They're all exactly the same, they just 126 00:08:21,746 --> 00:08:25,674 use different sets of random coins. In a given iteration of this outer loop, 127 00:08:25,674 --> 00:08:28,724 we're just going to be doing straightforward local search. 128 00:08:28,724 --> 00:08:32,926 So we have to specify what's the space of solutions? Well those are just all of the 129 00:08:32,926 --> 00:08:37,028 ways of assigning the invariables to true and false, all possible assignments. 130 00:08:37,028 --> 00:08:39,382 We have to specify the neighboring solution. 131 00:08:39,382 --> 00:08:43,087 That's just going to be the one we discussed, so 2 assignments will be 132 00:08:43,087 --> 00:08:47,269 neighboring if they differ only in the flip of a value of a single variable. 133 00:08:47,269 --> 00:08:50,852 We have to make a decision about where we start the local search. 134 00:08:50,852 --> 00:08:55,217 We're going to do it in just the obvious randomized way, from a uniform and random 135 00:08:55,217 --> 00:08:59,055 assignment of the variables. After we've settled on a random initial 136 00:08:59,055 --> 00:09:03,506 assignment, we just do local search. That is, we just keep flipping variables, 137 00:09:03,506 --> 00:09:07,443 trying to improve the quality of the current assign Now one thing that's going 138 00:09:07,443 --> 00:09:11,475 to be a little bit different from this algorithm, relative to the generic local 139 00:09:11,475 --> 00:09:15,242 search algorithm we discussed in the previous video, is I'm going to place an 140 00:09:15,242 --> 00:09:18,847 a priori bound on how many local moves we're going to do before we give up. 141 00:09:18,847 --> 00:09:22,622 One obvious motivation for that is, if we want a polynomial time algorithm 142 00:09:22,622 --> 00:09:26,424 [INAUDIBLE] This will ensure that the algorithm will not run for too many 143 00:09:26,424 --> 00:09:29,011 steps. So the magic number, which we'll motivate 144 00:09:29,011 --> 00:09:33,034 when we analyze the algorithm, is 2n^2. That's how many variable flips we're 145 00:09:33,034 --> 00:09:36,892 going to make before we give up and return to the next independent trial. 146 00:09:36,892 --> 00:09:40,072 in the outer for loop. Remember n denotes the number of 147 00:09:40,072 --> 00:09:43,010 variables. In each iteration of the inner for loop 148 00:09:43,010 --> 00:09:47,723 we first check just to see if the current assignment is in fact satisfiable, if it 149 00:09:47,723 --> 00:09:51,490 satisfies all the clauses. If so, we're done, we halt and report 150 00:09:51,490 --> 00:09:54,444 that back. Suppose the current assignment is not 151 00:09:54,444 --> 00:09:57,400 satisfy. What does that mean? That means there's 152 00:09:57,400 --> 00:10:01,462 one clause or maybe many clauses which are not currently satisfied. 153 00:10:01,462 --> 00:10:06,152 SO, for example, maybe there's some clause involving the variables X3 and X7. 154 00:10:06,152 --> 00:10:09,962 And the we unfortunately set X3 to be true, and X7 to be false. 155 00:10:09,962 --> 00:10:13,246 And that's exactly the joint value forbidden by this clause. 156 00:10:13,246 --> 00:10:15,493 That is, maybe the clause is not x3 or x7. 157 00:10:15,493 --> 00:10:19,104 So what do we do next? Well next we do an iteration of local search. 158 00:10:19,104 --> 00:10:22,774 We try and improve our assignment. How do we do that? Well we pick an 159 00:10:22,774 --> 00:10:27,195 unsatisfied clause.If there are many such clauses, we pick one arbitrarily and we 160 00:10:27,195 --> 00:10:31,110 try to make amends with this clause by flipping the values with one of the 161 00:10:31,110 --> 00:10:34,921 variables in the clause. So, in our example we're either going to 162 00:10:34,921 --> 00:10:38,558 flip x3 from true to false. That would satisfy the clause. 163 00:10:38,558 --> 00:10:41,154 Or we're going to flip x7 from false to true. 164 00:10:41,154 --> 00:10:45,702 That would also satisfy the clause. Assuming the clause is not x3 or x7. 165 00:10:45,702 --> 00:10:49,867 Now either one of these variable flips would succeed in changing this clause 166 00:10:49,867 --> 00:10:54,272 from unsatisfied to satisfied, and you could think of various clever heuristics 167 00:10:54,272 --> 00:10:58,332 about which of the 2 variables you decide to flip, but we're going to take the 168 00:10:58,332 --> 00:11:02,193 simplest way forward. We're just going to pick Pick between the 169 00:11:02,193 --> 00:11:07,205 two 50-50 so again how do we modify the assignment which choose an arbitrary 170 00:11:07,205 --> 00:11:12,217 unsatisfied clause, we pick one or two variables in the clause uniformly or 171 00:11:12,217 --> 00:11:15,382 random and we flip the value of that variable. 172 00:11:15,382 --> 00:11:19,247 Now what makes this algorithm so frightening to think about and my best 173 00:11:19,247 --> 00:11:23,387 guess for the reason why this very elegant algorithm wasn't analysed before 174 00:11:23,387 --> 00:11:27,207 1991, is that you can do some serious damage when you flip one of these 175 00:11:27,207 --> 00:11:30,172 variables. I mean, yeah, the var, the constraint you 176 00:11:30,172 --> 00:11:34,122 started with is going to go from unsatisfied to satisfied but for all you 177 00:11:34,122 --> 00:11:38,412 know all these other clauses are going to go from satisfied to unsatisfied. 178 00:11:38,412 --> 00:11:43,418 [INAUDIBLE] If, for example, you take the variable x3 and you flip it from true to 179 00:11:43,418 --> 00:11:46,413 false, well yeah, that's great for this clause. 180 00:11:46,413 --> 00:11:49,984 It was not x3 or 7. It becomes true, it becomes satisfied, 181 00:11:49,984 --> 00:11:54,644 but maybe there are a zillion other clause where x3 appears un-negated, it's 182 00:11:54,644 --> 00:11:59,004 x3 or something else and perhaps by switching x3 to go from true to false a 183 00:11:59,004 --> 00:12:01,646 bunch of those have now become unsatisfied. 184 00:12:01,646 --> 00:12:06,311 So in no way are you always increasing the number of satisfied clauses when you 185 00:12:06,311 --> 00:12:10,687 do an iteration of this local search. It's very non standard local search 186 00:12:10,687 --> 00:12:14,328 algorithm in that sense. To complete the description of this 187 00:12:14,328 --> 00:12:18,992 algorithm I have to tell you what happens if it never finds a satisfying 188 00:12:18,992 --> 00:12:21,499 assignment. Of course, if it does find such an 189 00:12:21,499 --> 00:12:26,205 assignment, it quits while it's ahead, it just returns that satisfying assignment. 190 00:12:26,205 --> 00:12:30,459 But if they're all after these 2N^2*LogN steps it's never found a satisfying 191 00:12:30,459 --> 00:12:33,038 assignment, it does something very arrogant. 192 00:12:33,038 --> 00:12:37,342 It just declares that well, if I didn't find a satisfying assignment, I think 193 00:12:37,342 --> 00:12:40,782 that one doesn't exist. Here is 2 obvious, positive statement we 194 00:12:40,782 --> 00:12:44,192 could make about this randomized local search algorithm for 2-SAT. 195 00:12:44,192 --> 00:12:48,382 First of all, it runs in polynomial time, and that's with probability 1, no matter 196 00:12:48,382 --> 00:12:50,912 how the coin flips or how the algorithms play out. 197 00:12:50,912 --> 00:12:54,922 That's because we explicitly control the number of iterations of local search. 198 00:12:54,922 --> 00:12:58,732 It's big o of n^2 log n, so even with the sloppiest implementation you could 199 00:12:58,732 --> 00:13:01,272 imagine of this algorithm, it's going to run. 200 00:13:01,272 --> 00:13:04,830 Run in polynomial time. Let's turn to the issue of correctness, 201 00:13:04,830 --> 00:13:09,120 and let's separate two side instances into those that are satisfiable, where 202 00:13:09,120 --> 00:13:13,202 there exists a satisfying assignment, and those that are unsatisfiable. 203 00:13:13,202 --> 00:13:17,431 The second obvious good property of this local search algorithm is that it's 204 00:13:17,431 --> 00:13:21,724 always going to be correct, if you feed into it in an unsatisfiable instance. 205 00:13:21,724 --> 00:13:25,541 Why? But what's the algorithm going to do on such an instance, well it's going to 206 00:13:25,541 --> 00:13:29,308 rummuage around amongst the possible assignments for these 2n square logN 207 00:13:29,308 --> 00:13:33,050 steps, trying out different ones, obviously none of them will be satisfying 208 00:13:33,050 --> 00:13:36,552 'cause there are no satisfying assignments, and at the end a the day the 209 00:13:36,552 --> 00:13:40,482 algorithm will correctly conclude that the instance is in fact unsatisfiable. 210 00:13:40,482 --> 00:13:46,074 But the key question is, what happens on satisfiable instances. 211 00:13:46,074 --> 00:13:52,769 If there is somewhere out there in the exponentially big space of assignments 212 00:13:52,769 --> 00:13:58,582 one that satisfies all of the assignments, is this algorithm going to 213 00:13:58,582 --> 00:14:04,118 find one in its mere 2n'2*logN steps. Now I have to tweak that question a 214 00:14:04,118 --> 00:14:06,872 little bit. This is, after all, a randomized 215 00:14:06,872 --> 00:14:11,100 algorithm and there's some tiny probability that the coin flips could 216 00:14:11,100 --> 00:14:15,462 conspire to stymie the algorithm from finding a satisfying assignment. 217 00:14:15,462 --> 00:14:20,267 So, what I really mean is, could it be the case that with probability very close 218 00:14:20,267 --> 00:14:24,853 to one on every satisfiable 2-SAT instance. This simple randomized local 219 00:14:24,853 --> 00:14:27,976 search algorithms, actually going to come up with a satisfying assignment.