My favorite NP-complete problem!
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 34 | |
| Author | ||
| License | CC Attribution - ShareAlike 3.0 Unported: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/38557 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
Bangbangcon (!!CON 2016)18 / 34
3
15
16
17
18
19
24
28
30
32
34
00:00
Computer animationJSONXML
00:15
Complete metric spaceHyperbolic functionSlide ruleXMLProgram flowchartComputer animation
00:42
Complete metric spaceFloating pointComputational complexity theoryComputer animation
01:04
Electronic mailing listData structureOrder (biology)Element (mathematics)Social classMoment (mathematics)Revision controloutputRight angleQuicksortComputer animation
02:50
Computer animation
03:16
NP-hardValue-added networkRight angleStructural loadComputer animation
04:03
Data miningWord2 (number)CASE <Informatik>Line (geometry)LengthScheduling (computing)Boolean satisfiability problemComputer animation
04:59
Boolean satisfiability problemAlgorithmBookmark (World Wide Web)Boolean satisfiability problemReverse engineeringWell-formed formulaPotenz <Mathematik>Multiplication signInverter (logic gate)Odds ratioVariable (mathematics)CASE <Informatik>Computer animation
07:13
Binary fileLevel (video gaming)Linear mapIntegerNP-completeBoolean satisfiability problemMultiplication signAlgorithmHamiltonian (quantum mechanics)Electronic mailing listMathematicianTouch typingPoint (geometry)CASE <Informatik>FamilyOptimization problemHamiltonian pathComputer animationDiagram
08:43
Multiplication signComputer animation
09:17
Noise (electronics)EvoluteIRIS-TProcess (computing)2 (number)Computer animation
09:57
IRIS-TInheritance (object-oriented programming)Computer animation
10:42
EmailGame theoryVideoconferencingVideoconferencingMultiplication signFraction (mathematics)1 (number)Sampling (statistics)Point (geometry)Grass (card game)Neighbourhood (graph theory)Thread (computing)Right angleSoftware bugElectronic mailing listComputer-assisted translationMusical ensembleGoodness of fitFamilyLengthGroup actionCoefficient of determinationComputer animation
12:49
Game theoryEmailSet (mathematics)NumberDifferent (Kate Ryan album)Group actionConstraint (mathematics)Software bugSubsetFraction (mathematics)Line (geometry)Point (geometry)Covering spaceNP-completeVideoconferencingHypothesisSet (mathematics)Computer scienceTheory of relativityComputer animation
14:59
VideoconferencingPlanningNP-completeSinc functionCanonical ensembleComputer animation
15:15
Set (mathematics)AlgorithmComputer animation
15:31
Computer animation
16:09
Power (physics)FreewareComputer animation
Transcript: English(auto-generated)
00:20
You know, I was going to start by saying that I had been looking forward to this all day, and then after that last talk I didn't want to 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 going to suck.
00:50
F11 doesn't work. This computer stuff is really complicated. Fortunately, Leo told me I can go right up until 5 o'clock, so if I could take a couple extra minutes, that's cool.
01:03
All right. Let's see. There we go. All right. 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, it's everything cool?
01:26
Well, I could have just stepped back. 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.
01:42
Kind of a dopey example is sorting. So like if you're not doing the sorting yourself, somebody comes along and says, well, here's the sorted version of the list you're trying to sort, and you just got to make sure that the elements are all the same in both lists, and then you check the one that the other person gave you and make sure the elements are in ascending order. It's okay. Yeah, that is sorted. You can do that efficiently.
02:02
And there's actually an easier way, which is 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 you take the input list, and you sort the input list, and then you compare it to see if they're the same. So that was kind of silly.
02:20
Problems that are easy to solve necessarily are easy to check the solutions to. Make sure you solve it, and then you see if what you got is the same as right. But there's more interesting NP problems, which we'll see in a moment. Some people are probably wondering, what does NP stand for, or why is it NP? And NP stands for ... Sorry.
02:47
It's not important. Okay, but not all problems are easy to solve like sorting, and it's quite possible that
03:03
you have a problem where it's hard to find a solution, but if somebody hands you something they claim as a solution, it's easy to check whether they're telling you the truth. And my favorite example of that is ... This is terrible. Is moving van loading.
03:20
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'd only put it in sideways, everything else would have gone in.
03:42
Well, okay, so it can be really hard to pack a moving van. Who's moved? Yeah, okay, right. 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.
04:01
So there's a familiar example of another NP problem. And let's see what else. Now all the text is too small. Crossword puzzles, right? Could be really hard to solve the crossword puzzle, but if somebody hands you one that's already filled in, you just gotta check to make sure each word matches the clue, and that the words all line up, and that'll be quick.
04:22
Conference scheduling, I'm not gonna 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 know 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
04:42
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. Alright, so of these NP problems, there's one that is super special, called SAT, which
05:03
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?
05:20
And it's clearly an NP, because if somebody came and magically said, oh yeah, make this one true, this one true, that one false, this one true, you could check just by evaluating the formula to see if it came out to be true, or whether they were telling you correctly that it was a solution. But, it could, at least in principle, be very difficult to define what values you assigned to the variables to make the formula true, and there might not be any.
05:44
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.
06:01
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
06:22
every other problem in NP. And so, for this reason, we say that this 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
06:44
able to solve NP, but it is not possible to have the reverse. So SAT is at least as hard as whatever your favorite problem is. And this discovery was independently by Cook and Levin.
07:01
Levin was in Russia, so he didn't hear about Cook, and he solved it around the same time but then didn't publish. I don't know. I don't know why I'm telling you this. It's not important. All right. Who's that? Let's see. The other thing that's interesting about this NP-complete is it turns out not just SAT is NP-complete. There turned out to be a large family of NP-complete problems, and this mathematician
07:25
named Karp discovered the following year, there are a whole bunch of them, and he gave a list of 21 NP-complete problems. One of them is SAT. One is this thing called 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
07:45
more than once, and then 19 others of various interest. 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
08:00
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 is a huge, huge family of these things, and we can't solve any of these.
08:21
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 and 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?
08:41
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, then you can remember a time before Elmo, and
09:03
anyway. So this is Elmo, who is beloved of toddlers. And wait a minute, where'd my ... There we go. This is my toddler.
09:20
She's now 11. She was a very demanding kid. She's like, 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 optimized
09:41
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 take care of the kid all day, and then she'd have to eat lunch, and she couldn't eat lunch. So she would take, this is Iris, she would take Iris and prop her up in this device
10:02
you see, which supports the kid, and it's got a bunch of entertaining things. The kid can revolve, but can't actually go anywhere, and would then park her in front of Sesame Street to watch Elmo's World, which lasts 20 minutes. And during this 20 minutes, she would be able to sneak off and make lunch, and eat it. And that was her like 20 minutes away from the kid.
10:22
This thing I have, we found out is called by parents, is called a neglecto saucer. Iris was obsessed with Elmo, and it turns out Elmo is like everywhere, and we were going up the stairs once, for example, and Iris is like, it's Elmo!
10:41
And this is what she saw on the stairs. All right, 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,
11:05
or should I read it aloud? I got, read it? Read some of it. Babies, bananas, baths, bicycles, birds, birthdays, books, brushing teeth, bugs, cats, dancing, dogs, drawing, ears, exercise, families.
11:22
Good, yeah. So this is a typical, this is not by any means the complete list, but it's a good sample. All right, then you don't have to catch these live, they also distribute them on,
11:42
it used to be a 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 that they could be delivered to Iris on demand, they always have three.
12:05
So here we see, this one's dancing, music, and books, and that's the title of the video release, dancing, music, and books, and then here's one called hands, ears, and feet, and you can see there's a common thread, each one has like a theme, right? Hands, ears, and feet, they go together, and, oops, sorry, sometimes they have,
12:22
you know, a different title, like this one's wake up with Elmo, but it packages together the three related segments on sleeping, getting dressed, and brushing your teeth, and this one is called people in your neighborhood, and it packages together the three segments on firefighters, lifeguards, and nurses, two minutes, we're gonna be cool, you can stop telling me, I'm gonna finish on time.
12:42
In fact, I could die grass at this point. Okay, so here's the constellation of Elmo's world segments, a small fraction of them, and I've circled the related groups, right, and so some of these are related, some aren't,
13:01
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 got the question, if you're designing these video releases, how do you pick the groups of three? And it should be clear there's some constraints on this, you can't put the same segment
13:22
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'd 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, here's
13:41
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, well, 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
14:04
we have to include all of them. And so there's a kind of a weird interplay of constraints here, right, 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
14:23
hit everything. And where are we going with this? I know Leo's getting nervous, but... So my favorite NP-complete problem is this one from Karp from 1972, the original paper that identified these 21 problems, called Exact Cover by Three Sets, which the computer
14:41
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.
15:02
Exactly. And there isn't anything else to say about it. So one of the canonical, original NP-complete problems from Richard Karp's original paper in 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.
15:22
Not in 1972, and not 30 years ago, and not today. And so how did they solve this problem? And the answer is, they couldn't. They couldn't, because this one is about flowers, bananas, and hair.
15:57
Thank you very much. Ooh, ooh, wait.
Recommendations
Series of 10 media
Series of 30 media