Mark Dominus: >> Oh, it changed resolution on me! Something is not happening here. We should have tested this earlier. Fortunately I've got the slides on the portable storage. Let me adjust the resolution from this end. Maybe it'll be happier. Fortunately... We've got 17 minutes. Yeah. I see the two monitors. Hang on a second. I've just get to tell it to merge them or whatever it is, in a minute. I don't remember how to do this. There's a button to push. Oh, this is really... No. Wait. That's upside down. That's not it. No, but I can adjust it to whatever seems to be... Uh-oh. I made a big mistake here. Which is I turned off my monitor. And... Linux. Maybe it'll... Oh, it came back! Hold on a sec. Please work, please work, please work! You have a backup computer? I really wanna use this one. This is so dumb of me... Okay. Let me try something. Yeah. Give me your backup computer. Leo Franchi: >> Stay tuned. This talk is gonna be awesome. The real NP-complete problem is projecting your slides. Mark Dominus: >> Monitor management under Linux. Let's see how this worked. Now what do we do. There it is? Is the monitor working? I can't see. Leo Franchi: >> Woo! Mark Dominus: >> Yeah. That's lovely. Thanks. And now... I was gonna start by saying that I had been looking forward to this all day, and then after that last talk, I didn't wanna go at all, because it was so good. And then all this stuff happened. And this morning, I adjusted the slides so the folks in the back would be able to read them, and now I don't have that adjustment anymore. I'm really sorry. This is gonna suck. (laughter) >> And F11 doesn't work. This computer stuff is really complicated. Fortunately, Leo told me I can go right up until 5:00. So if I can take a couple extra minutes, that's cool. All right. Let's see. There we go. All right. [Slide 2] So there's this class of problems called... NP. For which... What it means is that if somebody hands you a solution to the problem... Everything cool? Oh, okay. I could have just stepped back. All right. If somebody hands you a solution to the problem or something that they claim is a solution, you can fairly easily and efficiently decide whether they're telling you the truth or not. And lots and lots of problems are in this class. Kind of a dopey example is sorting. So... If you're not doing the sorting itself, somebody comes along and says... Here's the sorted version of the list that you're trying to sort, you've got to try to make sure that the elements are the same in both lists and then you check the one that the person gave you and check that the elements are in ascending order. You can do that efficiently. But there's an easier way. Since sorting is not hard to do efficiently anyway, you'll learn maybe how to do it in sophomore data structures class. You take the list that you're handed and take the input list and sort the input list and compare it to see if they're the same. So that was kind of silly. Problems that are easy to solve necessarily are easy to check the solutions to. You solve it and you see if what you got is the same as... Right. And so... But there's more interesting NP problems, which we'll see in a moment. Some people are probably wondering... What does NP stand for? Why is it NP? NP stands for... (coughing unintelligibly) >> It's not important. Okay. [Slide 3] But... Not all problems are easy to solve, like sorting. And it's quite possible that you have a problem where it's hard to find a solution. But if somebody hands you something they claim is a solution, it's easy to check whether they're telling you the truth. And my favorite example of that is... Oh, this is terrible. Is moving van loading. So you've got all your stuff out on the sidewalk. And the question is: Does it all fit into the van? And you start loading it in. And when you're all done, there's seven things left on the sidewalk. And is that because you have too much stuff and the van's not big enough, or is it because you messed up somewhere back on item 15, and if you had only put it in sideways, everything else would have gone in. So it can be really hard to pack a moving van. Who's moved? But... But if somebody comes to you, puts the stuff into the van, and says -- look, it's all packed! It fit! It's really easy to verify whether they're telling the truth. You just shut the door. And if it shuts all the way, oh my gosh, thank you! So there's a familiar example of another NP problem. And let's see what else. Ugh. Now all the text is too small. Cross word puzzles. Right? Could be really hard to solve the crossword puzzle, but if somebody hands you one that's already filled in, you just have to check if it matches the clue and that the words line up. Conference scheduling. I'm not going to go into that at length, because we've only got one room here. It's kind of a trivial case. If you've ever done homework, you can toil over the homework problems for hours and hours, but the grader can check the answers in seconds, sometimes. So it's a lot easier to check to see if you get the right answer than it is to come up with the right answer. So there's a lot of these problems where it's hard to find a solution but it's easy to check, if you're given one. All right. [Slide 4] So of these NP problems, there's one that is super special. Called SAT. Which is short for satisfiability. And the problem is that somebody gives you a formula involving ands and ors and nots and variables, and the question is: Is there a way to assign True and False values to the variables so that the formula comes out to be true? And it's clearly an NP, because if someone said... Make this one true, this one true, that one false... You can check by evaluating the formula to see if it came out to be True to tell whether they were correctly telling you it was a solution. But at least in principle it could be difficult to define what values you assign to the variables. To make the formula true. And there might not be any. You could, of course, try every possible assignment. But that takes too long, if there's a lot of variables. It takes exponential time. And in fact, nobody knows a good algorithm for this problem that works in every case efficiently. Now, here's the thing that's magical about this problem. If you did have a good algorithm for solving it, you could take any problem in NP, any NP problem whatsoever, and you could take your algorithm for SAT, and you could convert it into an efficient algorithm for solving whatever your favorite NP problem is. So solving this one SAT problem, finding an efficient algorithm for it, would solve every other problem in NP. So for this reason, we say that the SAT problem is NP-complete. A solution for SAT would completely solve NP. Another thing we sometimes say is that... SAT is the hardest problem in NP. Because it's possible that you might have a good algorithm to solve your favorite problem, but not be able to solve NP. But it is not possible to have the reverse. And SAT is at least as hard as whatever your favorite problem is. And this discovery was independently by Cook and Levin. Levin was in Russia, so he didn't hear about Cook. And he solved it around the sametime but didn't publish. I don't know why I'm telling you this. It's not important. [Slide 5] Who's that? The other thing that's interesting about this NP-complete is it turns out not just SAT is NP-complete. There turn out to be a large family of NP-complete problems. And this mathematician named Karp discovered the following year there are a whole bunch of them. And he gave a list of 21NP-complete problems. One is SAT, one is Hamiltonian cycle. Which is -- can you find a path that hits all the cities and returns to its starting point but doesn't touch any of the cities more than once? And then 19 others of various interest. And so these things actually turn out to be common, and a solution to any one of them, an efficient algorithm to solve any one of these 21 problems, would completely solve NP, and therefore would solve the other 20. They're all very well studied problems, and still, nobody knows a good algorithm for any of them. Because if they did, they would know a good algorithm for all of them. It's kind of surprising. Since then, people have discovered hundreds of NP-complete problems. There's a huge, huge family of these things, and we can't solve any of these. We can solve them in special cases, we can find almost optimal solutions, we have algorithms that are really good, except for a few weird examples where they blow up. But everything goes wrong somehow. Which is kind of weird. All right. So my favorite one of these... We have to have a little digression now. Hey, Leo, how much time have I got? Leo Franchi: >> Five minutes. [Slide 6] Mark Dominus: >> Awesome! This little guy here is Elmo. Who knows Elmo? Okay. Because Elmo has dominated Sesame Street for, like, the last 30 years. If you're old and bald like me, you can remember a time before Elmo. And... (sighing) Uh... Um... So this is Elmo. Who is beloved of toddlers. And... Wait a minute. Where did my... Uh-uh. [Slide 7] Here we go. This is my toddler. She's now 11. She was a very demanding kid. Some kids you can just leave them and then you come back later. They've amused themselves. They were like... Put their foot in their mouth or whatever kids do. She would... If you left the room for 30 seconds, she would make this noise that is... Is optimized over millions of years of evolution to be the most unpleasant possible sound. And since I had a day job, my wife was left doing this, and she would, like, take care of the kid all day, and then she would have to eat lunch, and she couldn't eat lunch. So she would take this... This is Iris. She would take Iris and prop her up in this device you see, which supports the kid, and it's got a bunch of entertaining things. The kid can resolve but can't actually go anywhere. And would park her in front of Sesame Street to watch Elmo's World, which lasts 20 minutes, and she would be able to make lunch and eat it. And that was her 20 minutes away from the kid. This thing... I found out... Is called a Neglect-O-Saucer. Iris was obsessed with Elmo, and it turns out Elmo is everywhere, and we were going up the stairs once, for example, and Iris is like... Aggh! That's Elmo. [Slide 8] And this is what she saw on the stairs. All right. [Slide 9] So what is Elmo's World about? It's 20 minutes long, as I said, and every 20 minute segment is about some topic that's of interest to toddlers. Such as... Can you folks in the back actually see this list? Or should I read it aloud? Lindsey Kuper: >> Read it. Read some of it. Mark Dominus: >> Read some of it. Babies, bananas, baths, cycles, birds, birthdays, books, brushing teeth, bugs, cats, dancing, dogs... Lindsey Kuper: >> Okay, that's good. Mark Dominus: >> Good. Yeah. So this is a typical... This is not by any means the complete list. But... It's a good sample. All right. [Slide 10] You don't have to catch these live. They also distribute them on... It used to be video cassette. Now of course it's DVD. And since they want the video cassettes and the DVDs to be uniform length, I guess an hour, they would parcel these out in groups of three. Three episodes per video release. So, for example... And we of course owned many of these, so they could be delivered to Iris on demand... They always have three. So here we see... This one is Dancing, Music, and Books. That's the title of the video release. Here's one called Hands, Ears, and Feet. Each one has a common theme. They go together. Sometimes they have a different title. Like this one is Wake Up with Elmo, but it packages sleeping, getting dressed, and brushing your teeth, and this is people in your neighborhood. It's Firefighters, Lifeguards, and Nurses. You don't have to keep telling me. I'm gonna finish on time. In fact, I could digress at this point. [Slide 11] So here's the constellation of Elmo's World segments. A small fraction of them. And I've circled the related groups. Right? So some of these are related. Some aren't. If you put together a video release called... On Shoes, Bugs, and Drawing, people would be puzzled, and that apparently is considered a no-no. So you've got the question... If you're designing these video releases, how do you pick the groups of three? And it should be clear there are some constraints on this. You can't put the same segment onto two different video releases. Because then the person who pays for it is gonna say... Hey, I got cheated. I paid for three but I've already got this one. And similarly, you've got a certain number of segments. You would like to include every one of them on some video release. So the question is... You have a bunch of groupings... Which I'm gonna show you. Let's say... [Slide 12] Here's a hypothetical collection of acceptable groupings. And each acceptable group of three is now surrounded by a colored wiggly line. And you wanna say... Okay. I wanna pick the groups of three that make the acceptable video releases. But... No two groups of three can overlap, because that would put the same segment on two different videos, and we have to include all of them. So there's a kind of a weird interplay of constraints here. Because if I decide to put the getting dressed in with shoes and jackets, that forecloses the possibility of doing getting dressed, brushing teeth, sleeping. Right? And so I can pick some of these, but they have to not overlap. And they have to somehow hit everything. And where are we going with this? I know Leo is getting nervous. So... [Slide 13] My favorite NP-complete problem is this one from Karp, from 1972, the original paper that identified these 21 problems called... Exact cover by 3-sets. Which... The computer science people call X3C. Because XC3 would have been too obvious. X3C. And at this point I would stop and I would explain in detail what X3C is. Except I did. It's that. Exactly. And there isn't anything else to say about it. So... One of the canonical original NP-complete problems from Richard Karp's paper from 1972 is the problem of how to plan Elmo's World video releases. And since it's NP-complete, there's no known good algorithm for it, not in 1972 and not 30 years ago, and not today. So how did they solve this problem? And the answer is... [Slide 14] They couldn't. They couldn't. (applause) Because... This one is about flowers... Bananas... And hair. (laughter) [Slide 15] >> Thank you very much. (applause)