WEBVTT - Algorithms In The Blood: The P vs. NP Problem 0:00:03.120 --> 0:00:05.920 Welcome to Stuff to Blow your Mind from how Stop 0:00:05.920 --> 0:00:15.600 works dot com. Hey, welcome to Spectable in your Mind. 0:00:15.600 --> 0:00:18.000 My name is Robert Lamb and I'm Joe McCormick. And 0:00:18.079 --> 0:00:20.640 today we're going to be taking a look at issue 0:00:20.840 --> 0:00:25.600 in computer science. Uh funny enough, I'd say that's not 0:00:25.720 --> 0:00:28.319 one of the sciences we dip into very frequently on 0:00:28.360 --> 0:00:31.120 this podcast. Yes, and I mean really, we should probably 0:00:31.120 --> 0:00:33.040 just remind everyone to stick with us, trust us on 0:00:33.080 --> 0:00:35.479 this one. Uh, don't be scared off by the computer 0:00:35.560 --> 0:00:38.400 science thing, don't be scared off by the P versus 0:00:38.560 --> 0:00:42.360 NP thing. It's it's it's all gonna make a type 0:00:42.360 --> 0:00:45.720 of sense at the end, hopefully. But I'm wondering if 0:00:45.760 --> 0:00:48.559 maybe we should dip into computer science more often because 0:00:49.000 --> 0:00:50.559 or at least wherever we can find a way to 0:00:50.600 --> 0:00:54.400 make the contents of it reasonably concrete, because, let's be honest, 0:00:54.480 --> 0:00:58.280 as we've discovered in researching this episode, it's very abstract, 0:00:58.400 --> 0:01:00.520 very difficult, and a lot of times hard to come 0:01:00.560 --> 0:01:03.440 up with ways of explaining that makes sense just just 0:01:03.520 --> 0:01:07.920 talking about it without visual aids or watching programs execute 0:01:07.959 --> 0:01:11.000 as an example. Yeah, it's definitely one of those topics 0:01:11.040 --> 0:01:13.760 that it's a swimming pool of a topic in which 0:01:14.080 --> 0:01:18.280 there is no gradual deepening from the kitty area to 0:01:18.319 --> 0:01:21.160 the deep end. It's just shallow, and at times it 0:01:21.160 --> 0:01:25.199 feels too shallow, and then you're immediately out of your depth. Yeah. 0:01:25.240 --> 0:01:27.840 But if you're thinking, kind of computer science, really does 0:01:27.880 --> 0:01:30.000 that fit with the show? Hold on for a second, 0:01:30.000 --> 0:01:33.000 because I think it does. Um. Computer science to me 0:01:33.120 --> 0:01:37.000 is a fascinating subject. Uh, and it's not just limited 0:01:37.040 --> 0:01:40.399 to how computers work. So my advice is, when you 0:01:40.400 --> 0:01:44.600 think about the idea of computer science, forget the computer 0:01:44.720 --> 0:01:47.160 sitting in front of you. That's not all it is. 0:01:47.200 --> 0:01:51.560 Computer science is really something more akin to the philosophy 0:01:51.640 --> 0:01:56.280 of logic, understanding the the underlying sorcery of how logic 0:01:56.320 --> 0:02:00.000 and math work in the universe we inhabit, and especially 0:02:00.120 --> 0:02:03.640 the science of how problems are solved, and certainly when 0:02:03.640 --> 0:02:06.080 you start bringing math into the equation here as well, 0:02:06.120 --> 0:02:08.960 I mean you're talking we're talking about the essentially the 0:02:09.040 --> 0:02:12.480 very fabric of the universe. We're talking about either the 0:02:12.480 --> 0:02:14.680 fabric of the universe, either the way the universe works 0:02:14.760 --> 0:02:17.200 or this perfect creation that humans have come up with 0:02:17.600 --> 0:02:21.080 that so accurately describes how the universe works, and that 0:02:21.160 --> 0:02:23.680 is pretty mind blowing territory. Well, either way you look 0:02:23.680 --> 0:02:26.880 at it, there is something mystical about about the math 0:02:27.000 --> 0:02:29.679 that we walk on every day, that you know, that 0:02:29.760 --> 0:02:32.640 makes up the fabric and the logic math beneath the 0:02:32.680 --> 0:02:34.520 math beneath our feet. You know, if you go with 0:02:34.600 --> 0:02:37.519 the Max teg Mark idea of the mathematical universe that 0:02:37.639 --> 0:02:39.760 some people don't like this idea because, like I don't 0:02:39.840 --> 0:02:42.560 understand what that means. But at least it's a very 0:02:42.600 --> 0:02:46.320 intriguing idea. I think it. His idea is that the 0:02:46.440 --> 0:02:50.440 underlying basis of all reality not just as described by math, 0:02:50.520 --> 0:02:54.560 but is math, and the universe is a mathematical object. 0:02:55.600 --> 0:02:57.480 But we're gonna get back to this idea of problem 0:02:57.600 --> 0:03:00.600 solving because today we want to focus on algori rhythms 0:03:00.639 --> 0:03:04.399 and on the inherent logic of problem solving in our universe, 0:03:04.760 --> 0:03:07.840 with some attention to a special example of one really 0:03:07.840 --> 0:03:12.160 interesting outstanding problem in computer science, and that's the P 0:03:12.680 --> 0:03:16.000 versus n P issue. If you've never heard of this before, 0:03:16.040 --> 0:03:18.560 don't worry. We'll explain what the terms mean in a 0:03:18.639 --> 0:03:21.880 simplified manner. And uh I at this point also do 0:03:21.960 --> 0:03:23.800 want to give a shout out to our listener Jim 0:03:23.800 --> 0:03:26.480 in New Jersey, who has been encouraging me over email 0:03:26.520 --> 0:03:29.480 to tackle this issue for a while despite all the challenges, 0:03:29.520 --> 0:03:32.640 and has also sent some really helpful, uh really helpful 0:03:32.639 --> 0:03:35.680 guides and explainers on some stuff he he learned about 0:03:35.680 --> 0:03:38.720 this when he was in graduate school. Yeah, indeed, and 0:03:38.840 --> 0:03:40.440 uh and I think this is great too because this 0:03:40.480 --> 0:03:43.080 episode is coming on the heels of, first of all, 0:03:43.160 --> 0:03:46.760 the Wicked Problems episode that came out of a few 0:03:46.760 --> 0:03:50.720 weeks ago, as well as the more recent Cargo Cults 0:03:50.920 --> 0:03:55.280 episode which in which we discuss outside context problems a 0:03:55.320 --> 0:03:57.560 little bit as well. So it's it's perfectly fitting that 0:03:57.600 --> 0:04:00.760 we would discuss another problem. Well, well, what does it 0:04:00.880 --> 0:04:04.320 mean inherently to solve a problem? If you get into 0:04:04.320 --> 0:04:06.760 the theory of problem solving? What what what does this 0:04:06.800 --> 0:04:09.600 process look like? Well, when it comes down just to 0:04:09.640 --> 0:04:12.080 the basics open and this also kind of gets into 0:04:12.520 --> 0:04:15.000 the whole Wicked Problems area of like what's what's missing 0:04:15.000 --> 0:04:17.599 when you don't have, um, you know, everything you need 0:04:17.800 --> 0:04:20.280 to solve a problem for for a real problem, you 0:04:20.320 --> 0:04:22.240 have to be able to course do to find what 0:04:22.400 --> 0:04:24.960 the problem is a lot of a lot of attempts 0:04:25.000 --> 0:04:27.280 fail right there. Yeah, you've got to you've got to 0:04:27.320 --> 0:04:29.480 be able to say this is the thing you know, 0:04:29.560 --> 0:04:31.120 and then you and then you have to be able 0:04:31.160 --> 0:04:35.200 to measure your success and check the solution. So you 0:04:35.320 --> 0:04:37.279 essentially have to be able to say, hey, this is 0:04:37.320 --> 0:04:40.479 wrong because of X, and then if you then figure 0:04:40.480 --> 0:04:45.200 out what X is and see if the equation balances out. Um, 0:04:45.320 --> 0:04:47.240 it sounds pretty simple. But like I said, as we 0:04:47.279 --> 0:04:50.720 discussed in Wicked Problems, that's uh, it can be very 0:04:50.720 --> 0:04:54.600 difficult to do, especially in you know, the very complex 0:04:54.600 --> 0:04:57.760 social situations when you're dealing with with certainly some of 0:04:57.760 --> 0:04:59.680 the larger problems that we're going to talk about here, 0:05:00.400 --> 0:05:03.480 or even if you want to go into the simplest level, well, 0:05:03.520 --> 0:05:06.119 I mean depending on what you would call simple. In fact, 0:05:06.160 --> 0:05:08.480 what we're going to be getting into today is directly 0:05:08.520 --> 0:05:12.080 referred to as complexity theory. Uh. So maybe it's not 0:05:12.160 --> 0:05:14.160 so simple, but at least simple in terms of not 0:05:14.240 --> 0:05:17.640 involving uh phenomena in the real world, but just math, 0:05:18.120 --> 0:05:21.920 just math and logic and and true versus untrue and 0:05:22.040 --> 0:05:24.680 UH and algorithms. So I think it's time to pull 0:05:24.760 --> 0:05:27.839 back the curtain a little bit and reveal some of 0:05:27.880 --> 0:05:31.520 the deep weirdness of the nature of algorithms and problem 0:05:31.600 --> 0:05:34.400 solving in our universe. So let's look at this P 0:05:34.720 --> 0:05:38.200 versus MP problem. This is something that comes from two 0:05:38.200 --> 0:05:41.479 of the great minds of the twentieth century, Kurt Girdle 0:05:41.640 --> 0:05:45.880 and John von Neuman. And in nineteen fifty six, Kurt Girdle, 0:05:45.920 --> 0:05:49.440 who's a mathematician and logician, wrote a letter to John 0:05:49.480 --> 0:05:53.280 von Neuman which kicked off this quest to solve one 0:05:53.279 --> 0:05:56.560 of the biggest questions in computer science, the P versus 0:05:56.680 --> 0:05:59.440 n P issue. Now, who were these guys, but both 0:05:59.520 --> 0:06:04.160 were heightens of the twentieth century in terms of math, logic, 0:06:04.240 --> 0:06:08.000 and computers. Well. Godal is probably most famous for his 0:06:08.279 --> 0:06:12.520 first incompleteness theorem, and this states that any adequate um 0:06:12.640 --> 0:06:16.120 axiomatizeable theory that means, a theory that's based on self 0:06:16.160 --> 0:06:21.040 evident but unprovable proofs, is incomplete or inconsistent. Yeah, Girdle's 0:06:21.080 --> 0:06:24.240 whole incompleteness theorem set. He had a couple of his 0:06:24.360 --> 0:06:28.200 incompleteness theorems essentially amount to the idea that any mathematical 0:06:28.279 --> 0:06:32.360 system that makes sense will have some statements that are 0:06:32.400 --> 0:06:35.640 true yet impossible to prove. It's sort of the idea 0:06:35.680 --> 0:06:40.119 that you can't ever know everything about a self consistent system. Yeah, 0:06:40.160 --> 0:06:43.440 And the the the implication here, according to theoretical physicist 0:06:43.440 --> 0:06:46.880 and mathematician Freeman Dyson, who has is also quite a 0:06:46.920 --> 0:06:50.840 giant in the field, is that mathematics is inexhaustible, that 0:06:50.920 --> 0:06:54.280 no matter how many problems we solve, will inevitably encounter 0:06:54.400 --> 0:06:59.040 more unsolvable problems within the existing rules. I take comfort 0:06:59.080 --> 0:07:02.039 in that measure a few tility. Yeah, but there's also 0:07:02.120 --> 0:07:05.360 John von Neuman, the recipient of the letter. And von Neuman, 0:07:06.080 --> 0:07:08.560 I don't know what you've heard about him, but I'd 0:07:08.600 --> 0:07:11.760 say he's often considered one of the most intelligent people 0:07:11.800 --> 0:07:15.280 who ever lived that we know about at least, And 0:07:15.400 --> 0:07:18.040 so maybe we call him a mathematician and a physicist, 0:07:18.120 --> 0:07:20.440 but he made contributions to numerous fields. He was a 0:07:20.880 --> 0:07:24.080 modern Da Vinci kind of you know, a polymath and so, 0:07:24.240 --> 0:07:27.360 and that includes computer science, for example, the von Neuman 0:07:27.480 --> 0:07:30.440 architecture in the history of computer design, which is basically 0:07:30.560 --> 0:07:34.680 it's a way of controlling the interaction between processing operations 0:07:34.720 --> 0:07:37.520 the CPU and the memory of a computer and this 0:07:37.680 --> 0:07:40.840 letter in nineteen fifty six from Girdle to von Neuman 0:07:41.440 --> 0:07:44.600 started this process of looking into the question of whether 0:07:44.960 --> 0:07:48.560 P does or does not equal in P. Now, like 0:07:48.560 --> 0:07:51.400 I said, we're about to explain what all the terms 0:07:51.400 --> 0:07:53.600 here mean. But I do want to note at the 0:07:53.600 --> 0:07:56.600 outset of this explanation that you know, on the show 0:07:56.640 --> 0:07:58.840 we always try to do our best to present our 0:07:58.880 --> 0:08:02.800 subjects accurately but then at the same time be understandable 0:08:02.840 --> 0:08:05.480 to the average person. And this, this P versus INP 0:08:05.640 --> 0:08:08.800 issue in complexity theory is probably the most difficult and 0:08:08.840 --> 0:08:11.640 abstract subject I've ever tried to cover on a podcast. 0:08:12.480 --> 0:08:14.360 So we'll have to do our best to explain the 0:08:14.400 --> 0:08:18.160 issue and its implications without losing you in asphyxiating clouds 0:08:18.160 --> 0:08:21.360 of abstraction. Yeah, I mean basically that the house stuff 0:08:21.400 --> 0:08:26.640 works mission overall is to demystify your science and UH 0:08:27.000 --> 0:08:29.040 topics like this can be a bit difficult because you 0:08:29.120 --> 0:08:32.400 don't want to through the explanation just mystify it even 0:08:32.400 --> 0:08:34.880 more for the average listener exactly right. So this is 0:08:34.960 --> 0:08:38.479 necessarily going to involve a lot of simplified versions of principles. 0:08:38.480 --> 0:08:41.320 We won't be able to go down uh, and explore 0:08:41.360 --> 0:08:44.880 all of the complex details behind these principles. But we 0:08:44.960 --> 0:08:48.320 hope that you computer scientists and mathematicians out there will 0:08:48.360 --> 0:08:50.800 not be too scandalized or think we're doing violence to 0:08:50.840 --> 0:08:55.679 your subject. Anyway, here we go. So we we've got 0:08:55.679 --> 0:08:57.920 to start with the concept of algorithms. What what is 0:08:57.960 --> 0:09:01.720 an algorithm? Well, I'd say an algorithm is a self 0:09:01.840 --> 0:09:06.240 contained list of instructions to solve a problem. You've got 0:09:06.240 --> 0:09:08.680 a goal, and then you make a step by step 0:09:08.880 --> 0:09:11.920 list of things to do that gets you to the goal. 0:09:12.360 --> 0:09:15.600 A common example within a computer program would be a 0:09:15.640 --> 0:09:20.960 subroutine designed to sort a list of things. That's an algorithm. Yeah, 0:09:21.000 --> 0:09:23.600 and you know, algorithms are something we encounter on a 0:09:24.160 --> 0:09:27.640 just on a daily basis, especially online. I mean Facebook, Google. 0:09:27.720 --> 0:09:30.360 Both of these depend on ever changing algorithms to decide 0:09:30.400 --> 0:09:33.800 what you see and don't see on your feeds and 0:09:33.800 --> 0:09:35.600 on your search results. Yeah, and I think that's a 0:09:35.600 --> 0:09:38.559 great example of how complex algorithms can get. You've got 0:09:38.600 --> 0:09:41.319 the simple sorting algorithm on one hand, and then you've 0:09:41.400 --> 0:09:45.440 got the stuff that decides whether you only see political 0:09:45.559 --> 0:09:48.360 articles you agree with, or whether you sometimes see stuff 0:09:48.360 --> 0:09:50.840 that's going to make you mad. So when you're designing 0:09:50.840 --> 0:09:54.560 algorithms in in a computer science arena, or really to 0:09:54.600 --> 0:09:57.280 solve any problem, but we're mostly gonna be talking about 0:09:57.320 --> 0:10:01.920 computer programs. You compare how much time it takes to 0:10:02.080 --> 0:10:05.440 solve a problem with an algorithm given the scope of 0:10:05.480 --> 0:10:08.520 a problem. So this is usually expressed in terms of 0:10:08.920 --> 0:10:11.880 inputs versus time. So I want to give a quick 0:10:11.880 --> 0:10:15.199 example with sorting. Like I said, you say, you're given 0:10:15.240 --> 0:10:18.400 a spreadsheet that includes a list of all the James 0:10:18.400 --> 0:10:22.600 Bond movies that exist currently in a random order, and 0:10:22.640 --> 0:10:25.200 you've got to write a computer program that sorts all 0:10:25.240 --> 0:10:28.640 of those lists of James Bond movie titles into a 0:10:28.760 --> 0:10:31.880 list in the order they came out. How would you 0:10:31.920 --> 0:10:34.040 do that? Now, there are a lot of ways you 0:10:34.080 --> 0:10:37.080 actually could approach the problem, and that they don't all 0:10:37.120 --> 0:10:39.440 take the same amount of time. Some are much more 0:10:39.440 --> 0:10:43.120 efficient than others. Here's one example. You could create an 0:10:43.160 --> 0:10:47.439 algorithm that goes like this. Step one, rearrange the entire 0:10:47.520 --> 0:10:51.120 list at random. Step two, check each movie in the 0:10:51.160 --> 0:10:53.319 list to see if it came out before the next 0:10:53.320 --> 0:10:55.960 movie in the list. If the answer is yes, all 0:10:56.000 --> 0:10:58.640 the way down the line, then the list is sorted correctly, 0:10:58.760 --> 0:11:02.480 and you're done. If not, start over and rearrange it 0:11:02.640 --> 0:11:05.680 entirely randomly. Now, given enough time and a small enough 0:11:05.760 --> 0:11:09.600 data set, this algorithm will eventually finish by blind luck. 0:11:09.760 --> 0:11:14.920 Is just brute force burning through computer resources wastefully in 0:11:15.040 --> 0:11:18.640 order to eventually solve the problem by blind block. But 0:11:18.880 --> 0:11:21.560 there are also much more efficient ways you could go 0:11:21.640 --> 0:11:24.040 about it. For example, you could go down the list 0:11:24.120 --> 0:11:27.000 comparing each movie to the next, and if the second 0:11:27.040 --> 0:11:29.560 movie came out before the first, you switch their order 0:11:29.600 --> 0:11:32.120 on the list, and then go on like that. Uh, 0:11:32.160 --> 0:11:34.640 and then you do that until the list is sorted. 0:11:35.160 --> 0:11:38.880 But some problems are inherently a lot harder than others, 0:11:38.920 --> 0:11:42.959 and there aren't any algorithmic shortcuts like that that we 0:11:43.000 --> 0:11:45.520 know about. We don't know of any easy way to 0:11:45.600 --> 0:11:48.760 solve them. The only thing we know how to do 0:11:48.960 --> 0:11:52.040 is do that stupid brute force method where you just 0:11:52.120 --> 0:11:56.920 wastefully burned through computer resources until it's solved by time 0:11:57.040 --> 0:12:00.480 and force. And in fact, I'd like to make a 0:12:00.520 --> 0:12:03.760 comparison here in the you know, the efficient algorithm versus 0:12:03.920 --> 0:12:07.319 brute force methods to what you might see in animals 0:12:07.360 --> 0:12:10.520 in the wild using intelligence to solve a problem. So, 0:12:10.559 --> 0:12:13.240 like if you're hunting another animal, you could use a 0:12:13.320 --> 0:12:17.840 brute force method of just running after the animal until 0:12:17.920 --> 0:12:20.760 it is tired or until your muscles have allowed you 0:12:20.800 --> 0:12:23.360 to catch it, and then killing it with the strength 0:12:23.400 --> 0:12:25.720 of your muscles. That's sort of the brute force method. 0:12:26.120 --> 0:12:28.800 Or you could set a trap, or you could build 0:12:28.800 --> 0:12:31.720 a weapon that these are shortcuts that make the process 0:12:31.720 --> 0:12:34.120 of hunting a lot more efficient. Now here's where we 0:12:34.160 --> 0:12:37.559 get to our main terms in this discussion. P and 0:12:37.840 --> 0:12:41.400 n P. P is going to stand for polynomial time, 0:12:42.000 --> 0:12:46.320 and in P stands for nondeterministic polynomial time. You don't 0:12:46.320 --> 0:12:48.840 really need to remember that for the purpose of this discussion, 0:12:48.840 --> 0:12:51.120 because we're gonna make it a lot simpler. Yeah, I mean, 0:12:51.120 --> 0:12:52.640 this is one of the problems with the topic is 0:12:52.720 --> 0:12:55.720 that like just the word this, this the the the 0:12:55.760 --> 0:12:58.280 basic idea here of P and n P. There, it's 0:12:58.360 --> 0:13:02.600 so dry and unrelated, doble, But allow us to explain. Yeah, okay, 0:13:02.640 --> 0:13:05.560 so the real difference has to do with um processes 0:13:05.600 --> 0:13:09.800 of solving problems on a deterministic Turing machine, which is 0:13:09.840 --> 0:13:12.480 equivalent to the kind of computer you'd be using right now. 0:13:12.559 --> 0:13:17.760 You know, any device you have versus a hypothetical nondeterministic machine, 0:13:18.400 --> 0:13:21.280 which in theory you could say works by magically guessing 0:13:21.320 --> 0:13:24.160 the answers to questions and then just checking to see 0:13:24.160 --> 0:13:26.440 if the magic guess is correct. But, like we said, 0:13:26.920 --> 0:13:28.360 we don't want to get too bogged down in all 0:13:28.360 --> 0:13:32.880 those details. So here's the simplified version. P is a 0:13:32.920 --> 0:13:36.160 set of all problems that can be solved by an 0:13:36.200 --> 0:13:40.640 algorithm quickly or easily or efficiently. This is the easy 0:13:40.840 --> 0:13:44.280 the list of easy problems in computer science. N P, 0:13:44.559 --> 0:13:47.040 on the other hand, stands for answers that can be 0:13:47.160 --> 0:13:51.040 easily checked by a computer once you have them, but 0:13:51.120 --> 0:13:55.280 they can't necessarily be solved easily. Yeah, so it's difficult 0:13:55.280 --> 0:13:58.199 to place this in a non mathematical context. But one 0:13:58.200 --> 0:14:00.280 way I like to think about this is in terms 0:14:00.320 --> 0:14:04.160 of written reviews for for albums, for you know, for 0:14:04.160 --> 0:14:08.880 for musical albums, um. Because a good a good review, 0:14:08.920 --> 0:14:12.360 a good music review is difficult to write, uh, and 0:14:12.559 --> 0:14:15.240 hard to find and hard to find. Yeah, like in 0:14:15.280 --> 0:14:17.800 my own experience you often find I mean, I I 0:14:17.840 --> 0:14:20.640 write many reviews of stuff of stuff from time to time, 0:14:20.640 --> 0:14:24.040 and that alone is challenging enough for me but but yeah, 0:14:24.080 --> 0:14:26.520 when you even when you're looking out of the major publications, 0:14:27.040 --> 0:14:29.320 uh yeah, it's hard to find one that feels just right. 0:14:29.360 --> 0:14:33.840 It's uh. The average reader, though, can can swiftly judge 0:14:33.840 --> 0:14:36.800 to what extent they agree with the author, obviously, to 0:14:36.840 --> 0:14:39.400 what extent the author is just blowing smoke. We've all 0:14:39.400 --> 0:14:42.400 read those music reviews where you get the sense that 0:14:42.480 --> 0:14:45.160 the the author is really using the music as an 0:14:45.160 --> 0:14:48.400 excuse to sort of write his or her own poetry. 0:14:48.840 --> 0:14:52.560 Uh there on the page episodes actually just describing what 0:14:52.600 --> 0:14:55.920 the music is like. But but the reader knows. So 0:14:56.000 --> 0:14:58.680 the reader can can can look at the material and 0:14:58.760 --> 0:15:01.280 you either believe in or you don't. Either you buy 0:15:01.280 --> 0:15:04.080 into their opinion or you don't. Yeah, so you could. 0:15:04.200 --> 0:15:08.200 You don't have the algorithm internally to efficiently right this 0:15:08.320 --> 0:15:10.400 piece of writing yourself, but you know it when you 0:15:10.440 --> 0:15:13.880 see it exactly. Yeah. It's kind of like pornography, and 0:15:13.960 --> 0:15:15.800 that's it. It's right. You might not be able to 0:15:15.960 --> 0:15:20.040 define clearly the difference between art and pornography, but you 0:15:20.120 --> 0:15:22.600 know it when you see it. Once you have that 0:15:22.640 --> 0:15:26.880 answer certificate there, you can check and by golly, it 0:15:27.040 --> 0:15:29.920 checks out. And I like that because it also gives 0:15:29.920 --> 0:15:32.160 a whole new meaning to the P and to the NP. 0:15:32.280 --> 0:15:36.480 And now, so there are a couple of other terms 0:15:36.520 --> 0:15:41.280 that matter. There's MP hard, and this means that are 0:15:41.280 --> 0:15:45.320 problems that are as hard as any other MP problem essentially. 0:15:45.720 --> 0:15:48.360 And then there's also MP complete, which is a big 0:15:48.800 --> 0:15:51.080 issue in this arena, and this is problems that are 0:15:51.280 --> 0:15:54.800 m P and m P hard. So you you can 0:15:54.920 --> 0:15:57.400 check the answer once you have it in in a 0:15:57.440 --> 0:16:00.840 reasonable amount of time, and they're in P hard. Now, 0:16:00.880 --> 0:16:03.600 the interesting thing about MP complete problems is that it 0:16:03.680 --> 0:16:06.480 has been proved in the literature that if you have 0:16:06.600 --> 0:16:11.640 an algorithm that can efficiently solve one MP complete problem, 0:16:11.720 --> 0:16:15.400 it can be transposed to solve all of them. These 0:16:15.400 --> 0:16:18.880 problems reduced to each other. So if you if you 0:16:18.920 --> 0:16:21.840 can solve one MP complete problem and a reasonable amount 0:16:21.880 --> 0:16:25.920 of time, you have found the master key. And this 0:16:26.160 --> 0:16:29.680 in the universe kind of shrinks. Yeah, in response to this, 0:16:30.400 --> 0:16:33.040 So a classic example of an MP problem is the 0:16:33.120 --> 0:16:37.320 prime factorization problem that we use in encryption on the Internet. Again, 0:16:37.400 --> 0:16:39.000 we don't want you to get lost too much here, 0:16:39.040 --> 0:16:43.200 So here's the simple version with smaller numbers than usual. 0:16:43.400 --> 0:16:46.080 Let's say I just throw out a random number, and 0:16:46.160 --> 0:16:49.160 let's say it's a number of I don't know what's 0:16:49.160 --> 0:16:51.880 a good one skulls in a pile. So let's say 0:16:51.880 --> 0:16:54.840 I give you a number. Let's say there are seven 0:16:54.920 --> 0:16:58.880 hundred and twenty one thousand, four hundred twenty one skulls 0:16:58.960 --> 0:17:01.200 in a pile. It's a lot skulls, it is. Now, 0:17:01.320 --> 0:17:04.440 I tell you this number is the product of two 0:17:04.920 --> 0:17:08.680 prime numbers of skulls in a pile, but I don't 0:17:08.720 --> 0:17:12.320 tell you what they are. Now, how could you figure 0:17:12.359 --> 0:17:15.080 out what those two prime numbers of skulls in a 0:17:15.119 --> 0:17:18.879 pile are? For a computer with numbers this small, this 0:17:18.920 --> 0:17:21.320 wouldn't be all that big a deal. But we're we're 0:17:21.320 --> 0:17:25.040 gonna have to extrapolate too much bigger numbers. But for you, 0:17:25.240 --> 0:17:28.640 this would be really annoying to figure out, right, Oh yes, 0:17:28.760 --> 0:17:31.680 because there's no simple, efficient way to do it. You'd 0:17:31.680 --> 0:17:35.000 pretty much have to get out a huge list of 0:17:35.080 --> 0:17:39.640 all the prime numbers between zero and seven thousand, four 0:17:39.720 --> 0:17:44.400 hundred one and start trying multiplying them together to see 0:17:44.440 --> 0:17:46.719 if they give you the right answer. Yeah, And in 0:17:46.720 --> 0:17:50.200 this situation, I imagine it's like the opening scenes of Terminator, 0:17:50.720 --> 0:17:54.119 And I'm probably already pretty distracted by the Pyramids of 0:17:54.160 --> 0:17:57.720 Bone and the Hunter Killer. The Hunter Killers exactly how 0:17:57.920 --> 0:18:00.160 I'm not gonna have time for all this prime number nuns. Now, 0:18:00.160 --> 0:18:02.440 since we've solved the equals in p at this point, 0:18:02.520 --> 0:18:05.080 they don't have rubber skin anymore. They figured out how 0:18:05.119 --> 0:18:07.159 to how to get through the problem to make the 0:18:07.200 --> 0:18:10.000 bio org suits. So, yeah, you're you're in a real 0:18:10.119 --> 0:18:14.680 rush here. But anyway, back to the problem. Yeah, there's 0:18:14.720 --> 0:18:19.040 just no fast, simple, easy way to solve this. And 0:18:19.080 --> 0:18:21.520 if you use numbers large enough, this type of problem 0:18:21.640 --> 0:18:26.560 is excruciatingly slow, even for computers to conquer by brute force. 0:18:27.119 --> 0:18:30.399 But let's say I told you the two prime numbers 0:18:30.440 --> 0:18:32.800 are seven hundred and fifty seven and nine hundred and 0:18:32.880 --> 0:18:36.960 fifty three piles skulls in a pile. It would be 0:18:37.040 --> 0:18:39.760 trivially easy for you to check and see if that's 0:18:39.800 --> 0:18:41.960 the correct solution. You just have to multiply them and 0:18:42.000 --> 0:18:44.760 see if you get the right answer, and it takes 0:18:44.800 --> 0:18:46.600 almost no time at all. And in fact, I really 0:18:46.600 --> 0:18:48.560 only need to tell you one of the numbers because 0:18:48.560 --> 0:18:51.040 you already know what they're supposed to multiply too, so 0:18:51.080 --> 0:18:53.879 you could just divide that by the one number. So 0:18:53.960 --> 0:18:56.160 here's an example. This is a problem that if you're 0:18:56.160 --> 0:18:58.840 going to try to solve it starting with no information, 0:18:58.960 --> 0:19:02.160 it's just going to take ages. It's going to be impossible. 0:19:02.640 --> 0:19:07.119 But if you already know a selected answer to test, 0:19:07.200 --> 0:19:10.080 you can check and see if that answer is right. Yeah, 0:19:10.119 --> 0:19:12.560 I mean this brings to mind. Uh it's a bit 0:19:12.600 --> 0:19:14.520 like trying to crack a four number code on a 0:19:14.560 --> 0:19:17.640 simple combination lock right, And I'm talking about a human 0:19:17.680 --> 0:19:20.440 doing this, not a computer. So it would take me, 0:19:20.560 --> 0:19:23.200 as a human quite a while to test out all 0:19:23.320 --> 0:19:27.159 ten thousand possible solutions, but no time at all to 0:19:27.400 --> 0:19:30.359 check a solution that someone else had provided me. So 0:19:30.480 --> 0:19:32.880 you know, I'd be there all day just putting in 0:19:32.920 --> 0:19:35.520 each one of those ten thousand solutions. But but I 0:19:35.520 --> 0:19:39.199 can easily put in, you know, uh, thirty three sixty 0:19:39.200 --> 0:19:41.359 six and see if that is correct. You found a 0:19:41.440 --> 0:19:44.800 really interesting request for help on this subject in you 0:19:45.040 --> 0:19:49.360 Oh yeah, yeah, there was because I wanted to check 0:19:49.400 --> 0:19:51.080 to make sure that my math was right on how 0:19:51.080 --> 0:19:53.080 many possible combinations. I was pretty sure it was the 0:19:53.119 --> 0:19:56.719 ten by ten by ten by ten thing. But I 0:19:56.359 --> 0:19:58.760 I did one of those searchers to just see people 0:19:58.800 --> 0:20:02.280 asking math questions online. And I found one where, um, 0:20:02.480 --> 0:20:06.120 this user apparently had a combination lock or it maybe 0:20:06.119 --> 0:20:09.960 it was like a contractor's box, you know, like at 0:20:09.960 --> 0:20:12.480 a house we had real estate agent. Yeah, and she 0:20:12.480 --> 0:20:14.440 says it's like a thirty dollar box. So she didn't 0:20:14.480 --> 0:20:16.919 want to just have it, you know, cut into and 0:20:17.040 --> 0:20:19.760 ruin it in order to get the keys out. She 0:20:19.880 --> 0:20:21.800 wanted to, but she didn't know what the combo was, 0:20:22.200 --> 0:20:25.840 so she wanted to just enter all the possible combinations 0:20:25.880 --> 0:20:28.080 to get it. And here's the here's the caveat though 0:20:28.320 --> 0:20:32.840 she knows that no number was used uh more than 0:20:32.880 --> 0:20:36.920 once and that cut it down significantly, just just more 0:20:36.920 --> 0:20:41.160 than five thousand, yeah, just like or something. Yeah. And 0:20:41.160 --> 0:20:43.840 and the person who supplied the answer on this forum, 0:20:43.880 --> 0:20:47.640 they included a list of all of them for her convenience, so, um, 0:20:48.200 --> 0:20:49.720 and I don't know how that came out. I wonder 0:20:49.760 --> 0:20:52.840 if she then took that list and just painstakingly, uh 0:20:53.200 --> 0:20:55.359 spent the time to try each one out, or if 0:20:55.400 --> 0:20:59.639 she decided, you know, actually that inputting all those numbers 0:20:59.720 --> 0:21:01.920 is not worth the thirty dollars that I would save 0:21:02.040 --> 0:21:04.760 by keeping the box attacked. That sounds like a fun Saturday, 0:21:04.840 --> 0:21:07.199 you know, on the porch in front of the box 0:21:07.240 --> 0:21:11.640 with a case of beer. Hopefully it's nice weather. But anyway, 0:21:11.840 --> 0:21:15.680 So yeah, this is problems that can potentially be brutally 0:21:15.760 --> 0:21:18.320 hard to solve, but they're easy to check once you 0:21:18.359 --> 0:21:21.840 have a certificate of the answer. Another classic and often 0:21:21.920 --> 0:21:26.840 cited example of an MP complete problem is the traveling 0:21:26.920 --> 0:21:30.240 salesman problem. Now I think something is exciting because now 0:21:30.280 --> 0:21:34.280 we have something with more of an anthropomorphic name smply scenario. 0:21:34.359 --> 0:21:36.639 It's like the Infinity Hotel. Well, I want to change 0:21:36.640 --> 0:21:38.080 it up, and I want to call I want to 0:21:38.119 --> 0:21:42.159 call this the nationwide infection problem. So imagine that you 0:21:42.200 --> 0:21:45.240