WEBVTT - From the Vault: P vs. NP 0:00:05.720 --> 0:00:07.640 Hey, welcome to Stuff to Blow Your Mind. My name 0:00:07.720 --> 0:00:10.320 is Robert Lamb and I'm Joe McCormick, and it's Saturday. 0:00:10.360 --> 0:00:12.280 What does that mean, Robert, What means it's time to 0:00:12.320 --> 0:00:14.680 open the vault. It looks like it's already open, so 0:00:14.760 --> 0:00:16.960 let's get in there. There's a lot of P in here. 0:00:17.520 --> 0:00:20.599 There's also a lot of MP in here. Perhaps you 0:00:20.640 --> 0:00:25.439 can explain this to everybody. Smooth transition, Robert, very smooth. 0:00:25.560 --> 0:00:28.520 I like it. Uh. This is the episode on the 0:00:28.600 --> 0:00:33.720 P versus MP problem, a classic fascinating vexing problem in 0:00:34.280 --> 0:00:37.440 logic and math and computer science and uh. And in 0:00:37.479 --> 0:00:40.040 this episode we tackle the question of what it actually 0:00:40.080 --> 0:00:44.080 means to solve a problem. This originally aired on April twelve, 0:00:45.600 --> 0:00:48.040 and we're bringing it back for you now, so we 0:00:48.080 --> 0:00:53.440 hope you enjoy our exploration of the P versus MP problem. 0:00:55.480 --> 0:00:58.280 Welcome to Stuff to Blow your Mind from how Stuff 0:00:58.280 --> 0:01:07.920 Works dot com. Hey, welcome to Sceptable in your Mind. 0:01:07.959 --> 0:01:10.320 My name is Robert Lamb and I'm Joe McCormick. And 0:01:10.400 --> 0:01:12.959 today we're gonna be taking a look at the issue 0:01:13.200 --> 0:01:17.920 in computer science. Uh. Funny enough, I'd say that's not 0:01:18.040 --> 0:01:20.520 one of the science, as we dip into very frequently 0:01:20.560 --> 0:01:23.119 on this podcast. Yes, and I mean, really, we should 0:01:23.160 --> 0:01:25.280 probably just remind everyone to stick with us, trust us 0:01:25.280 --> 0:01:27.440 on this one. Uh, don't be scared off by the 0:01:27.440 --> 0:01:29.840 computer science thing. Don't be scared off by the P 0:01:30.440 --> 0:01:34.360 versus MP thing. It's it's it's all gonna make a 0:01:34.440 --> 0:01:37.920 type of sense at the end, hopefully. But I'm wondering 0:01:37.920 --> 0:01:40.440 if maybe we should dip into computer science more often 0:01:40.520 --> 0:01:42.800 because or at least wherever we can find a way 0:01:42.840 --> 0:01:46.240 to make the contents of it reasonably concrete, because, let's 0:01:46.240 --> 0:01:49.240 be honest, as we've discovered in researching this episode, it's 0:01:49.760 --> 0:01:52.560 very abstract, very difficult, and a lot of times hard 0:01:52.600 --> 0:01:55.320 to come up with ways of explaining that makes sense 0:01:55.400 --> 0:01:59.040 just just talking about it without visual aids or watching 0:01:59.080 --> 0:02:02.360 programs Exit Cute as an example. Yeah, it's definitely one 0:02:02.400 --> 0:02:05.160 of those topics that it's a swimming pool of a 0:02:05.240 --> 0:02:09.639 topic in which there is no gradual deepening from the 0:02:09.720 --> 0:02:12.800 kitty area to the deep end. It's just shallow, and 0:02:12.919 --> 0:02:16.120 at times it feels too shallow and then you're immediately 0:02:16.480 --> 0:02:18.639 out of your depth. Yeah, but if you're thinking of 0:02:18.760 --> 0:02:21.600 computer science, really does that fit with the show hold 0:02:21.639 --> 0:02:23.919 on for a second, because I think it does. Um. 0:02:24.160 --> 0:02:27.880 Computer science to me is a fascinating subject. Uh, and 0:02:28.000 --> 0:02:31.840 it's not just limited to how computers work. So my 0:02:31.880 --> 0:02:35.120 advice is, when you think about the idea of computer science, 0:02:35.639 --> 0:02:38.880 forget the computer sitting in front of you. That's not 0:02:38.960 --> 0:02:42.440 all it is. Computer science is really something more akin 0:02:42.560 --> 0:02:47.680 to the philosophy of logic, understanding the the underlying sorcery 0:02:47.800 --> 0:02:51.440 of how logic and math work in the universe we inhabit, 0:02:51.680 --> 0:02:55.520 and especially the science of how problems are solved. And 0:02:55.520 --> 0:02:57.840 certainly when you start bringing math into the equation here 0:02:57.960 --> 0:03:00.200 as well, I mean you're talking we're talking about the 0:03:00.800 --> 0:03:04.160 essentially the very fabric of the universe. We're talking about 0:03:03.960 --> 0:03:06.160 either the fabric of the universe, either the way the 0:03:06.240 --> 0:03:09.160 universe works, or this perfect creation that humans have come 0:03:09.240 --> 0:03:12.800 up with that so accurately describes how the universe works, 0:03:12.800 --> 0:03:15.720 and that is pretty mind blowing territory. Well, either way 0:03:15.720 --> 0:03:18.720 you look at it, there is something mystical about about 0:03:18.760 --> 0:03:21.920 the math that we walk on every day that you know, 0:03:21.960 --> 0:03:24.960 that makes up the fabric and the logic math, the 0:03:25.000 --> 0:03:26.840 math beneath our feet. You know, if you go with 0:03:26.919 --> 0:03:30.080 the max Tech mark idea of the mathematical universe. Some 0:03:30.080 --> 0:03:32.600 people don't like this idea because, like I don't understand 0:03:32.600 --> 0:03:35.920 what that means, but at least it's a very intriguing idea. 0:03:36.040 --> 0:03:40.200 I think his ideas that the underlying basis of all 0:03:40.360 --> 0:03:44.040 reality not just as described by math, but is math, 0:03:44.160 --> 0:03:48.400 and the universe is a mathematical object. But we're gonna 0:03:48.440 --> 0:03:51.000 get back to this idea of problem solving because today 0:03:51.040 --> 0:03:54.320 we want to focus on algorithms and on the inherent 0:03:54.400 --> 0:03:57.960 logic of problem solving in our universe, with some attention 0:03:58.000 --> 0:04:02.640 to a special example of one really interesting outstanding problem 0:04:02.720 --> 0:04:06.440 in computer science, and that's the P versus n P issue. 0:04:07.160 --> 0:04:09.040 If you've never heard of this before, don't worry. We'll 0:04:09.080 --> 0:04:12.000 explain what the terms mean in in a simplified manner. 0:04:12.560 --> 0:04:14.480 And uh I at this point also do want to 0:04:14.480 --> 0:04:16.880 give a shout out to our listener Jim in New Jersey, 0:04:16.960 --> 0:04:19.480 who has been encouraging me over email to tackle this 0:04:19.560 --> 0:04:22.200 issue for a while despite all the challenges, and has 0:04:22.240 --> 0:04:25.440 also sent some really helpful, uh really helpful guides and 0:04:25.520 --> 0:04:28.320 explainers on some stuff. He he learned about this when 0:04:28.320 --> 0:04:31.400 he was in graduate school. Yeah, indeed, and UH and 0:04:31.400 --> 0:04:33.320 I think this is great too, because this episode is 0:04:33.320 --> 0:04:36.240 coming on the heels of first of all, the Wicked 0:04:36.279 --> 0:04:40.120 Problems episode that came out a few weeks ago, as 0:04:40.160 --> 0:04:44.719 well as the more recent Cargo Cults episode which in 0:04:44.760 --> 0:04:48.000 which we discuss some outside context problems a little bit 0:04:48.000 --> 0:04:50.320 as well. So it's it's perfectly fitting that we would 0:04:50.560 --> 0:04:54.320 discuss another problem. Well, what does it mean inherently to 0:04:54.600 --> 0:04:57.240 solve a problem? If you get into the theory of 0:04:57.320 --> 0:05:00.960 problem solving? What what what does this process look like? Well, 0:05:01.080 --> 0:05:02.919 when it comes down just to the basics open and 0:05:02.960 --> 0:05:05.800 this also kind of gets into the whole Wicked Problems 0:05:05.839 --> 0:05:08.800 area of like, what's what's missing when you don't have, um, 0:05:08.920 --> 0:05:11.480 you know, everything you need to solve a problem for 0:05:11.480 --> 0:05:13.240 for a real problem, you have to be able to, 0:05:13.240 --> 0:05:16.160 of course, do to find what the problem is. A 0:05:16.160 --> 0:05:18.279 lot of a lot of attempts fail right there. Yeah, 0:05:18.360 --> 0:05:20.320 you've got to You've got to be able to say 0:05:20.440 --> 0:05:22.680 this is the thing you know and then you and 0:05:22.720 --> 0:05:24.800 then you have to be able to measure your success 0:05:25.279 --> 0:05:28.359 and check the solution. So you essentially have to be 0:05:28.400 --> 0:05:31.719 able to say, hey, this is wrong because of X. 0:05:31.760 --> 0:05:33.560 And then if you then figure out what x is 0:05:33.600 --> 0:05:38.080 and see if the equation balances out. Um, it sounds 0:05:38.080 --> 0:05:40.040 pretty simple. But like I said, as we discussed in 0:05:40.080 --> 0:05:43.640 Wicked problems, that's uh, it can be very difficult to do, 0:05:43.760 --> 0:05:48.400 especially in you know, the very complex social situations when 0:05:48.400 --> 0:05:50.960 you're dealing with with certainly some of the larger problems 0:05:50.960 --> 0:05:53.360 that we're going to talk about here, or even if 0:05:53.360 --> 0:05:56.120 you want to go into the simplest level, well, I mean, 0:05:56.200 --> 0:05:58.600 depending on what you would call simple. In fact, what 0:05:58.640 --> 0:06:01.200 we're going to be getting into today is directly referred 0:06:01.200 --> 0:06:04.960 to as complexity theory. Uh. So maybe it's not so simple, 0:06:05.000 --> 0:06:07.839 but at least simple in terms of not involving uh 0:06:08.200 --> 0:06:10.960 phenomena in the real world, but just math, just math 0:06:11.080 --> 0:06:15.560 and logic and and true versus untrue and UH and algorithms. 0:06:15.600 --> 0:06:17.880 So I think it's time to pull back the curtain 0:06:18.320 --> 0:06:21.440 a little bit and reveal some of the deep weirdness 0:06:21.480 --> 0:06:25.200 of the nature of algorithms and problem solving in our universe. 0:06:25.520 --> 0:06:28.640 So let's look at this P versus MP problem. This 0:06:28.760 --> 0:06:31.360 is something that comes from two of the great minds 0:06:31.400 --> 0:06:35.239 of the twentieth century, Kurt Girdle and John von Neuman, 0:06:35.760 --> 0:06:39.560 and in nineteen fifty six, Kurt Girdle, who's a mathematician 0:06:39.560 --> 0:06:43.120 and logician, wrote a letter to John von Neuman which 0:06:43.440 --> 0:06:46.320 kicked off this quest to solve one of the biggest 0:06:46.440 --> 0:06:50.440 questions in computer science, the P versus n P issue. Now, 0:06:50.480 --> 0:06:53.120 who were these guys, but both were titans of the 0:06:53.160 --> 0:06:57.680 twentieth century in terms of math, logic, and computers. Well. 0:06:57.720 --> 0:07:02.000 Godal is probably most famous for his first incompleteness theorem, 0:07:02.160 --> 0:07:06.760 and this states that any adequate um axiomatizeable theory that means, 0:07:06.839 --> 0:07:10.040 a theory that's based on self evident but unprovable proofs, 0:07:10.360 --> 0:07:15.840 is incomplete or inconsistent. Yeah. Girdle's whole incompleteness theorem set. Yeah, 0:07:15.840 --> 0:07:19.040 A couple of his incompleteness theorems essentially amount to the 0:07:19.080 --> 0:07:23.240 idea that any mathematical system that makes sense will have 0:07:23.440 --> 0:07:27.280 some statements that are true yet impossible to prove. It's 0:07:27.280 --> 0:07:29.680 sort of the idea that you can't ever know everything 0:07:29.760 --> 0:07:33.360 about a self consistent system. Yeah, and the the The 0:07:33.400 --> 0:07:37.240 implication here, according to theoretical physicist and mathematician Freeman Dyson, 0:07:37.440 --> 0:07:40.400 who has is also quite a giant in the field, 0:07:41.120 --> 0:07:44.160 is that mathematics is inexhaustible, that no matter how many 0:07:44.160 --> 0:07:49.200 problems we solve, will inevitably encounter more unsolvable problems within 0:07:49.480 --> 0:07:53.760 the existing rules. I take comfort in that measure of futility. Yeah, 0:07:53.800 --> 0:07:56.640 but there's also John von Neuman, the recipient of the letter. 0:07:56.760 --> 0:08:00.400 And von Neuman. I don't know what you've heard about him, 0:08:00.440 --> 0:08:03.000 but I'd say he's often considered one of the most 0:08:03.080 --> 0:08:06.520 intelligent people who ever lived that we know about at least, 0:08:07.560 --> 0:08:10.440 and so maybe we call him a mathematician and a physicist, 0:08:10.440 --> 0:08:12.800 but he made contributions to numerous fields. He was a 0:08:13.240 --> 0:08:16.600 modern Da Vinci kind of you know, a polymath, and 0:08:16.600 --> 0:08:19.680 and that includes computer science, for example, the von Neuman 0:08:19.840 --> 0:08:22.760 architecture in the history of computer design, which is basically 0:08:22.920 --> 0:08:27.000 it's a way of controlling the interaction between processing operations 0:08:27.040 --> 0:08:29.880 the CPU and the memory of a computer. And this 0:08:30.040 --> 0:08:33.240 letter in nineteen fifty six from Girdle to von Neumann 0:08:33.800 --> 0:08:36.920 started this process of looking into the question of whether 0:08:37.280 --> 0:08:40.880 P does or does not equal in P. Now, like 0:08:40.920 --> 0:08:43.720 I said, we're about to explain what all the terms 0:08:43.760 --> 0:08:45.920 here mean. But I do want to note at the 0:08:45.960 --> 0:08:48.920 outset of this explanation that you know, on this show 0:08:48.960 --> 0:08:51.200 we always try to do our best to present our 0:08:51.240 --> 0:08:55.120 subjects accurately, but then at the same time be understandable 0:08:55.160 --> 0:08:57.640 to the average person. And this, this P versus in 0:08:57.760 --> 0:09:01.040 P issue in complexity theory is probably the most difficult 0:09:01.040 --> 0:09:03.959 and abstract subject I've ever tried to cover on a podcast. 0:09:04.800 --> 0:09:06.720 So we'll have to do our best to explain the 0:09:06.720 --> 0:09:10.480 issue and its implications without losing you in asphyxiating clouds 0:09:10.480 --> 0:09:14.240 of abstraction. Yeah, I mean, basically, the House of Works 0:09:14.320 --> 0:09:18.760 UH mission overall is to demystify your science and UH 0:09:19.320 --> 0:09:21.400 topics like this can be a bit difficult because you 0:09:21.440 --> 0:09:24.720 don't want to through the explanation just mystify it even 0:09:24.760 --> 0:09:27.199 more for the average listener exactly right. So this is 0:09:27.280 --> 0:09:30.800 necessarily going to involve a lot of simplified versions of principles. 0:09:30.800 --> 0:09:33.680 We won't be able to go down uh and explore 0:09:33.720 --> 0:09:37.240 all of the complex details behind these principles, but we 0:09:37.320 --> 0:09:40.680 hope that you computer scientists and mathematicians out there will 0:09:40.679 --> 0:09:43.160 not be too scandalized or think we're doing violence to 0:09:43.200 --> 0:09:47.760 your subject. Uh. Anyway, here we go. So we we 0:09:47.840 --> 0:09:50.040 got to start with the concept of algorithms. What what 0:09:50.200 --> 0:09:53.640 is an algorithm? Well, I'd say an algorithm is a 0:09:53.720 --> 0:09:58.360 self contained list of instructions to solve a problem. You've 0:09:58.360 --> 0:10:00.600 got a goal, and then you make us step by 0:10:00.640 --> 0:10:03.800 step list of things to do that gets you to 0:10:03.840 --> 0:10:07.600 the goal. A common example within a computer program would 0:10:07.679 --> 0:10:11.160 be a subroutine designed to sort a list of things. 0:10:11.400 --> 0:10:15.000 That's an algorithm. Yeah, and you know, algorithms are something 0:10:15.000 --> 0:10:18.640 we encounter on a just on a daily basis, especially online. 0:10:18.640 --> 0:10:21.199 I mean Facebook, Google. Both of these depend on ever 0:10:21.320 --> 0:10:24.480 changing algorithms to decide what you see and don't see 0:10:25.200 --> 0:10:27.439 on your feeds and on your search results. Yeah, and 0:10:27.480 --> 0:10:29.959 I think that's a great example of how complex algorithms 0:10:30.000 --> 0:10:33.200 can get. You've got the simple sorting algorithm on one hand, 0:10:33.240 --> 0:10:36.240 and then you've got the stuff that decides whether you 0:10:36.360 --> 0:10:39.680 only see political articles you agree with or whether you 0:10:39.760 --> 0:10:42.400 sometimes see stuff that's going to make you mad. So, 0:10:42.400 --> 0:10:46.400 when you're designing algorithms in in a computer science arena, 0:10:46.480 --> 0:10:49.040 or really to solve any problem, but we're mostly gonna 0:10:49.080 --> 0:10:53.520 be talking about computer programs, you compare how much time 0:10:53.640 --> 0:10:57.199 it takes to solve a problem with an algorithm, given 0:10:57.240 --> 0:10:59.960 the scope of a problem. So this is usually expressed 0:11:00.040 --> 0:11:03.720 in terms of inputs versus time. So I want to 0:11:03.720 --> 0:11:07.040 give a quick example with sorting. Like I said, you say, 0:11:07.040 --> 0:11:10.160 you're given a spreadsheet that includes a list of all 0:11:10.200 --> 0:11:13.960 the James Bond movies that exist currently in a random order, 0:11:14.840 --> 0:11:17.280 and you've got to write a computer program that sorts 0:11:17.320 --> 0:11:20.880 all of those lists of James Bond movie titles into 0:11:20.920 --> 0:11:24.120 a list in the order they came out. How would 0:11:24.160 --> 0:11:26.240 you do that? Now, there are a lot of ways 0:11:26.280 --> 0:11:29.160 you actually could approach the problem, and that they don't 0:11:29.200 --> 0:11:31.560 all take the same amount of time. Some are much 0:11:31.559 --> 0:11:35.320 more efficient than others. Here's one example. You could create 0:11:35.360 --> 0:11:39.280 an algorithm that goes like this. Step one, rearrange the 0:11:39.480 --> 0:11:43.360 entire list at random. Step two, check each movie in 0:11:43.360 --> 0:11:45.360 the list to see if it came out before the 0:11:45.400 --> 0:11:48.120 next movie in the list. If the answer is yes, 0:11:48.160 --> 0:11:50.120 all the way down the line, then the list is 0:11:50.160 --> 0:11:54.000 sorted correctly and you're done. If not, start over and 0:11:54.200 --> 0:11:57.400 rearrange it entirely randomly. Now, given enough time and a 0:11:57.480 --> 0:12:01.040 small enough data set, this algorithm will if eventually finished 0:12:01.080 --> 0:12:04.800 by blind luck. It is just brute force burning through 0:12:04.840 --> 0:12:09.320 computer resources wastefully in order to eventually solve the problem 0:12:09.400 --> 0:12:13.120 by blind block. But there are also much more efficient 0:12:13.120 --> 0:12:15.640 ways you could go about it. For example, you could 0:12:15.679 --> 0:12:18.480 go down the list comparing each movie to the next, 0:12:18.559 --> 0:12:20.839 and if the second movie came out before the first, 0:12:20.920 --> 0:12:22.960 you switch their order on the list and then go 0:12:23.040 --> 0:12:25.959 on like that. Uh, and then you do that until 0:12:26.000 --> 0:12:29.600 the list is sorted. But some problems are inherently a 0:12:29.600 --> 0:12:34.480 lot harder than others, and there aren't any algorithmic shortcuts 0:12:34.520 --> 0:12:36.680 like that that we know about. We don't know of 0:12:36.760 --> 0:12:40.200 any easy way to solve them. The only thing we 0:12:40.280 --> 0:12:43.400 know how to do is do that stupid brute force 0:12:43.480 --> 0:12:47.280 method where you just wastefully burned through computer resources until 0:12:47.400 --> 0:12:52.280 it's solved by time and force. And in fact, I'd 0:12:52.320 --> 0:12:54.360 like to make a comparison here in the you know, 0:12:54.440 --> 0:12:58.360 the efficient algorithm versus brute force methods, to what you 0:12:58.440 --> 0:13:01.440 might see in animals in the wild using intelligence to 0:13:01.480 --> 0:13:04.680 solve a problem. So like, if you're hunting another animal, 0:13:04.920 --> 0:13:08.720 you could use a brute force method of just running 0:13:08.760 --> 0:13:11.959 after the animal until it is tired or until your 0:13:12.040 --> 0:13:14.760 muscles have allowed you to catch it, and then killing 0:13:14.800 --> 0:13:16.959 it with the strength of your muscles. That's sort of 0:13:17.000 --> 0:13:20.040 the brute force method. Or you could set a trap, 0:13:20.200 --> 0:13:23.000 or you could build a weapon that these are shortcuts 0:13:23.040 --> 0:13:25.440 that make the process of hunting a lot more efficient. 0:13:25.760 --> 0:13:28.600 Now here's where we get to our main terms in 0:13:28.640 --> 0:13:31.599 this discussion, P and n P. P is going to 0:13:31.720 --> 0:13:37.079 stand for polynomial time and n P stands for nondeterministic 0:13:37.160 --> 0:13:39.920 polynomial time. You don't really need to remember that for 0:13:40.040 --> 0:13:42.120 the purpose of this discussion, because we're gonna make it 0:13:42.160 --> 0:13:43.800 a lot simpler. Yeah, I mean, this is one of 0:13:43.840 --> 0:13:46.360 the problems with the topic, is that like just the 0:13:46.400 --> 0:13:49.040 word just this the the the basic idea here of 0:13:49.080 --> 0:13:53.040 P and MP there, it's so dry and unrelatable. But 0:13:53.440 --> 0:13:56.200 allow us to explain. Yeah, okay, So the real difference 0:13:56.240 --> 0:13:59.040 has to do with um processes of solving problems on 0:13:59.120 --> 0:14:02.800 a determinus dick Turing machine, which is equivalent to the 0:14:02.880 --> 0:14:05.120 kind of computer you'd be using right now, you know, 0:14:05.440 --> 0:14:11.000 any device you have, versus a hypothetical nondeterministic machine, which 0:14:11.000 --> 0:14:13.760 in theory you could say works by magically guessing the 0:14:13.840 --> 0:14:16.679 answers to questions and then just checking to see if 0:14:16.679 --> 0:14:19.320 the magic guess is correct. But, like we said, we 0:14:19.320 --> 0:14:21.280 don't want to get too bogged down in all those details. 0:14:21.280 --> 0:14:25.880 So here's the simplified version. P is a set of 0:14:25.920 --> 0:14:30.080 all problems that can be solved by an algorithm quickly 0:14:30.200 --> 0:14:33.560 or easily or efficiently. This is the easy. The list 0:14:33.600 --> 0:14:37.120 of easy problems in computer science. N P, on the 0:14:37.120 --> 0:14:40.720 other hand, stands for answers that can be easily checked 0:14:40.720 --> 0:14:43.960 by a computer once you have them, but they can't 0:14:43.960 --> 0:14:48.000 necessarily be solved easily. Yeah. So it's difficult to place 0:14:48.080 --> 0:14:50.760 this in a non mathematical context. But one way I 0:14:50.800 --> 0:14:53.720 like to think about this is in terms of written reviews, 0:14:53.880 --> 0:14:59.160 for for albums, for for for musical albums. Um, because 0:14:59.400 --> 0:15:03.080 a good a good review, a good music review is 0:15:03.080 --> 0:15:05.880 is difficult to write, uh, and hard to find and 0:15:06.000 --> 0:15:08.400 hard to find. Yeah, Like in my own experience, you 0:15:08.440 --> 0:15:11.240 often find I mean, I I write many reviews of 0:15:11.280 --> 0:15:14.120 stuff of stuff from time to time, and that alone 0:15:14.160 --> 0:15:16.640 is challenging enough for me. But but yeah, when you 0:15:16.760 --> 0:15:19.760 even when you're looking out of the major publications, uh, yeah, 0:15:19.760 --> 0:15:22.680 it's hard to find one that feels just right. It's Uh. 0:15:23.000 --> 0:15:26.400 The average reader, though, can can swiftly judge to what 0:15:26.520 --> 0:15:29.560 extent they agree with the author, obviously, to what extent 0:15:29.640 --> 0:15:32.080 the author is just blowing smoke. We've all read those 0:15:32.160 --> 0:15:35.280 music reviews where you get the sense that the the 0:15:35.360 --> 0:15:38.160 author is really using the music as an excuse to 0:15:38.280 --> 0:15:41.720 sort of write his or her own poetry. Uh, they're 0:15:41.760 --> 0:15:45.320 on the page as opposed actually describing what the music 0:15:45.440 --> 0:15:48.760 is like. But but the reader knows. So the reader 0:15:48.800 --> 0:15:52.160 can can can look at the material and either believe 0:15:52.200 --> 0:15:54.360 them or you don't. Either you buy into their opinion 0:15:54.480 --> 0:15:57.080 or you don't. Yeah, so you could. You don't have 0:15:57.160 --> 0:16:01.920 the algorithm internally to efficiently right this piece of writing yourself, 0:16:01.920 --> 0:16:04.520 but you know it when you see it exactly. Yeah, 0:16:04.560 --> 0:16:07.120 it's kind of like pornography in that sens right. You 0:16:07.240 --> 0:16:10.480 might not be able to define clearly the difference between 0:16:10.760 --> 0:16:13.520 art and pornography, but you know it when you see it. 0:16:14.240 --> 0:16:16.920 Once you have that answer certificate there, you can check 0:16:17.440 --> 0:16:21.440 and by golly, it checks out. And I like that 0:16:21.480 --> 0:16:23.520 because it also gives a whole new meaning to the 0:16:23.520 --> 0:16:27.720 P and to the MP and H. Now, so there 0:16:27.760 --> 0:16:30.280 are a couple of other terms that matter there. There's 0:16:30.440 --> 0:16:34.440 MP hard, and this means that are problems that are 0:16:34.480 --> 0:16:38.400 as hard as any other MP problem essentially. And then 0:16:38.400 --> 0:16:41.600 there's also MP complete, which is a big issue in 0:16:41.640 --> 0:16:43.880 this arena, and this is problems that are m P 0:16:44.160 --> 0:16:47.720 and n P hard so you you can check the 0:16:47.760 --> 0:16:50.640 answer once you have it in in a reasonable amount 0:16:50.640 --> 0:16:53.880 of time, and their MP hard. Now, the interesting thing 0:16:53.920 --> 0:16:56.920 about MP complete problems is that it has been proved 0:16:57.000 --> 0:16:59.840 in the literature that if you have an algorithm that 0:17:00.000 --> 0:17:04.560 and efficiently solve one MP complete problem, it can be 0:17:04.640 --> 0:17:09.000 transposed to solve all of them. These problems reduced to 0:17:09.160 --> 0:17:12.040 each other. So if you if you can solve one 0:17:12.200 --> 0:17:15.320 MP complete problem in a reasonable amount of time, you 0:17:15.440 --> 0:17:19.560 have found the master key. And this in the universe 0:17:19.640 --> 0:17:23.440 kind of shrinks in response to this. So a classic 0:17:23.480 --> 0:17:27.320 example of an MP problem is the prime factorization problem 0:17:27.359 --> 0:17:29.800 that we use in encryption on the Internet. Again, we 0:17:29.800 --> 0:17:31.520 don't want you to get lost too much here, so 0:17:32.119 --> 0:17:35.920 here's the simple version with smaller numbers than usual. Let's 0:17:35.920 --> 0:17:38.760 say I just throw out a random number, and let's 0:17:38.760 --> 0:17:41.520 say it's a number of I don't know what's a 0:17:41.560 --> 0:17:44.320 good one skulls in a pile. So let's say I 0:17:44.400 --> 0:17:47.600 give you a number. Let's say there are seven hundred 0:17:47.600 --> 0:17:51.359 and twenty one thousand, four hundred twenty one skulls in 0:17:51.400 --> 0:17:55.160 a pile. It is now I tell you this number 0:17:55.240 --> 0:17:59.240 is the product of two prime numbers of skulls in 0:17:59.240 --> 0:18:03.560 a pile, but I don't tell you what they are. Now, 0:18:03.600 --> 0:18:06.760 how could you figure out what those two prime numbers 0:18:06.760 --> 0:18:09.879 of skulls in a pile are? For a computer with 0:18:10.080 --> 0:18:12.800 numbers this small, this wouldn't be all that big a deal. 0:18:12.880 --> 0:18:15.920 But we're we're gonna have to extrapolate too much bigger numbers. 0:18:16.640 --> 0:18:20.160 But for you, this would be really annoying to figure out, right, 0:18:21.119 --> 0:18:24.040 because there's no simple efficient way to do it. You'd 0:18:24.040 --> 0:18:27.320 pretty much have to get out a huge list of 0:18:27.440 --> 0:18:31.960 all the prime numbers between zero and seven thousand, four 0:18:32.040 --> 0:18:36.720 hundred one and start trying multiplying them together to see 0:18:36.760 --> 0:18:39.040 if they give you the right answer. Yeah, and in 0:18:39.080 --> 0:18:42.520 this situation, I imagine it's like the opening scenes of Terminator, 0:18:43.040 --> 0:18:46.439 and I'm probably already pretty distracted by the Pyramids of 0:18:46.480 --> 0:18:50.400 Bone and the Hunter Killer, the Hunter Killers exactly, I'm 0:18:50.400 --> 0:18:52.480 not gonna have time for all this prime number nuns. Now, 0:18:52.480 --> 0:18:54.840 since we've solved p equals in p at this point, 0:18:54.840 --> 0:18:57.440 they don't have rubber skin anymore. They figured out how 0:18:57.440 --> 0:18:59.480 to how to get through the problem to make the 0:18:59.520 --> 0:19:02.359 bio or suits. So yeah, you're you're in a real 0:19:02.440 --> 0:19:07.040 rush here. But anyway, back to the problem. Yeah, there's 0:19:07.080 --> 0:19:11.399 just no fast, simple, easy way to solve this. And 0:19:11.440 --> 0:19:13.840 if you use numbers large enough, this type of problem 0:19:13.960 --> 0:19:18.919 is excruciatingly slow, even for computers to conquer by brute force. 0:19:19.440 --> 0:19:22.760 But let's say I told you the two prime numbers 0:19:22.760 --> 0:19:25.119 are seven hundred and fifty seven and nine hundred and 0:19:25.200 --> 0:19:29.320 fifty three piles skulls in a pile. It would be 0:19:29.359 --> 0:19:32.080 trivially easy for you to check and see if that's 0:19:32.119 --> 0:19:34.320 the correct solution. You just have to multiply them and 0:19:34.320 --> 0:19:37.119 see if you get the right answer, and that takes 0:19:37.119 --> 0:19:38.880 almost no time at all. And in fact, I'd really 0:19:38.960 --> 0:19:40.880 only need to tell you one of the numbers because 0:19:40.920 --> 0:19:43.359 you already know what they're supposed to multiply too, so 0:19:43.400 --> 0:19:46.199 you could just divide that by the one number. So 0:19:46.280 --> 0:19:48.480 here's an example. This is a problem that if you're 0:19:48.480 --> 0:19:51.200 going to try to solve it starting with no information, 0:19:51.280 --> 0:19:53.680 it's just going to take you ages. It's going to 0:19:53.760 --> 0:19:58.880 be impossible. But if you already know a selected answer 0:19:58.960 --> 0:20:01.199 to test, you can I can see if that answer 0:20:01.280 --> 0:20:04.480 is right. Yeah, I mean this brings to mind. Uh, 0:20:04.520 --> 0:20:06.440 it's a bit like trying to crack a four number 0:20:06.480 --> 0:20:09.400 code on a simple combination lock, right, And I'm talking 0:20:09.440 --> 0:20:12.040 about a human doing this, not a computer. So it 0:20:12.040 --> 0:20:14.800 would take me as a human quite a while to 0:20:14.840 --> 0:20:18.880 test out all ten thousand possible solutions, but no time 0:20:18.920 --> 0:20:21.560 at all to check a solution that someone else had 0:20:21.560 --> 0:20:23.880 provided me. So you know, I'd be there all day 0:20:23.920 --> 0:20:27.160 just putting in each one of those ten thousand solutions. 0:20:27.200 --> 0:20:30.160 But but I can easily put in you know, uh, 0:20:30.560 --> 0:20:33.000 thirty three sixty six and see if that is correct. 0:20:33.200 --> 0:20:36.880 You found a really interesting request for help on this subject, 0:20:36.880 --> 0:20:41.320 and you, oh, yeah, yeah, there was because I wanted 0:20:41.359 --> 0:20:43.119 to check to make sure that my math was right 0:20:43.160 --> 0:20:45.240 on how many possible combinations. I was pretty sure it 0:20:45.280 --> 0:20:47.520 was the ten by ten by ten by ten thing. 0:20:48.280 --> 0:20:50.560 But I I did one of those searchers to just 0:20:50.600 --> 0:20:54.800 see people asking math questions online, and I found one where, um, 0:20:54.840 --> 0:20:58.440 this user apparently had a combination lock or it maybe 0:20:58.480 --> 0:21:02.199 it was like a contract actor's box, you know, like 0:21:02.200 --> 0:21:04.400 at a house we have a real estate agent. Yeah, 0:21:04.480 --> 0:21:06.399 and she says it's like a thirty dollar box. So 0:21:06.440 --> 0:21:08.480 she didn't want to just have it, you know, cut 0:21:08.520 --> 0:21:11.280 into and ruin it in order to get the keys out. 0:21:12.040 --> 0:21:14.159 She wanted to, but she didn't know what the combo was, 0:21:14.560 --> 0:21:18.200 so she wanted to just enter all the possible combinations 0:21:18.240 --> 0:21:20.400 to get it. And here's the here's the caveat though 0:21:20.640 --> 0:21:25.520 she knows that no number was used, uh more than once, 0:21:26.320 --> 0:21:29.440 and that cut it down significantly, just just more than 0:21:29.480 --> 0:21:33.120 five thousand. Yeah, just was like five thousand forty or something. Yeah. 0:21:33.240 --> 0:21:36.160 And and the person who supply the answer on this forum, 0:21:36.200 --> 0:21:38.719 they included a list of all of them for her convenience. 0:21:39.320 --> 0:21:41.720 So um, I and I don't know how that came out. 0:21:41.760 --> 0:21:45.200 I wonder if she then took that list and just painstakingly, uh, 0:21:45.560 --> 0:21:47.719 spent the time to try each one out, or if 0:21:47.720 --> 0:21:52.000 she decided, you know, actually that inputting all those numbers 0:21:52.080 --> 0:21:54.280