June 9, 2018 • 54 mins
What does it mean to solve a problem in our universe? That's a trickier question than you might think, with some fairly high-stakes ramifications in the worlds of computing and even philosophy. In this episode of Stuff to Blow Your Mind, Robert Lamb and Joe McCormick explore the inherent logic of problem-solving in our universe, with some attention to a special example of an outstanding problem in computer science: P vs. NP. (Originally published April 12, 2016)
Learn more about your ad-choices at https://www.iheartpodcastnetwork.com
See omnystudio.com/listener for privacy information.
Mark as Played
Transcript
Episode Transcript
Available transcripts are automatically generated. Complete accuracy is not guaranteed.
Speaker 1 (00:05):
Hey, welcome to Stuff to Blow Your Mind. My name
is Robert Lamb and I'm Joe McCormick, and it's Saturday.
What does that mean, Robert, What means it's time to
open the vault. It looks like it's already open, so
let's get in there. There's a lot of P in here.
There's also a lot of MP in here. Perhaps you
can explain this to everybody. Smooth transition, Robert, very smooth.
I like it. Uh. This is the episode on the
(00:28):
P versus MP problem, a classic fascinating vexing problem in
logic and math and computer science and uh. And in
this episode we tackle the question of what it actually
means to solve a problem. This originally aired on April twelve,
and we're bringing it back for you now, so we
hope you enjoy our exploration of the P versus MP problem.
(00:55):
Welcome to Stuff to Blow your Mind from how Stuff
Works dot com. Hey, welcome to Sceptable in your Mind.
My name is Robert Lamb and I'm Joe McCormick. And
today we're gonna be taking a look at the issue
in computer science. Uh. Funny enough, I'd say that's not
(01:18):
one of the science, as we dip into very frequently
on this podcast. Yes, and I mean, really, we should
probably just remind everyone to stick with us, trust us
on this one. Uh, don't be scared off by the
computer science thing. Don't be scared off by the P
versus MP thing. It's it's it's all gonna make a
type of sense at the end, hopefully. But I'm wondering
if maybe we should dip into computer science more often
(01:40):
because or at least wherever we can find a way
to make the contents of it reasonably concrete, because, let's
be honest, as we've discovered in researching this episode, it's
very abstract, very difficult, and a lot of times hard
to come up with ways of explaining that makes sense
just just talking about it without visual aids or watching
programs Exit Cute as an example. Yeah, it's definitely one
(02:02):
of those topics that it's a swimming pool of a
topic in which there is no gradual deepening from the
kitty area to the deep end. It's just shallow, and
at times it feels too shallow and then you're immediately
out of your depth. Yeah, but if you're thinking of
computer science, really does that fit with the show hold
on for a second, because I think it does. Um.
(02:24):
Computer science to me is a fascinating subject. Uh, and
it's not just limited to how computers work. So my
advice is, when you think about the idea of computer science,
forget the computer sitting in front of you. That's not
all it is. Computer science is really something more akin
to the philosophy of logic, understanding the the underlying sorcery
(02:47):
of how logic and math work in the universe we inhabit,
and especially the science of how problems are solved. And
certainly when you start bringing math into the equation here
as well, I mean you're talking we're talking about the
essentially the very fabric of the universe. We're talking about
either the fabric of the universe, either the way the
universe works, or this perfect creation that humans have come
(03:09):
up with that so accurately describes how the universe works,
and that is pretty mind blowing territory. Well, either way
you look at it, there is something mystical about about
the math that we walk on every day that you know,
that makes up the fabric and the logic math, the
math beneath our feet. You know, if you go with
the max Tech mark idea of the mathematical universe. Some
(03:30):
people don't like this idea because, like I don't understand
what that means, but at least it's a very intriguing idea.
I think his ideas that the underlying basis of all
reality not just as described by math, but is math,
and the universe is a mathematical object. But we're gonna
get back to this idea of problem solving because today
(03:51):
we want to focus on algorithms and on the inherent
logic of problem solving in our universe, with some attention
to a special example of one really interesting outstanding problem
in computer science, and that's the P versus n P issue.
If you've never heard of this before, don't worry. We'll
explain what the terms mean in in a simplified manner.
(04:12):
And uh I at this point also do want to
give a shout out to our listener Jim in New Jersey,
who has been encouraging me over email to tackle this
issue for a while despite all the challenges, and has
also sent some really helpful, uh really helpful guides and
explainers on some stuff. He he learned about this when
he was in graduate school. Yeah, indeed, and UH and
I think this is great too, because this episode is
(04:33):
coming on the heels of first of all, the Wicked
Problems episode that came out a few weeks ago, as
well as the more recent Cargo Cults episode which in
which we discuss some outside context problems a little bit
as well. So it's it's perfectly fitting that we would
discuss another problem. Well, what does it mean inherently to
(04:54):
solve a problem? If you get into the theory of
problem solving? What what what does this process look like? Well,
when it comes down just to the basics open and
this also kind of gets into the whole Wicked Problems
area of like, what's what's missing when you don't have, um,
you know, everything you need to solve a problem for
for a real problem, you have to be able to,
of course, do to find what the problem is. A
(05:16):
lot of a lot of attempts fail right there. Yeah,
you've got to You've got to be able to say
this is the thing you know and then you and
then you have to be able to measure your success
and check the solution. So you essentially have to be
able to say, hey, this is wrong because of X.
And then if you then figure out what x is
and see if the equation balances out. Um, it sounds
(05:38):
pretty simple. But like I said, as we discussed in
Wicked problems, that's uh, it can be very difficult to do,
especially in you know, the very complex social situations when
you're dealing with with certainly some of the larger problems
that we're going to talk about here, or even if
you want to go into the simplest level, well, I mean,
depending on what you would call simple. In fact, what
(05:58):
we're going to be getting into today is directly referred
to as complexity theory. Uh. So maybe it's not so simple,
but at least simple in terms of not involving uh
phenomena in the real world, but just math, just math
and logic and and true versus untrue and UH and algorithms.
So I think it's time to pull back the curtain
a little bit and reveal some of the deep weirdness
(06:21):
of the nature of algorithms and problem solving in our universe.
So let's look at this P versus MP problem. This
is something that comes from two of the great minds
of the twentieth century, Kurt Girdle and John von Neuman,
and in nineteen fifty six, Kurt Girdle, who's a mathematician
and logician, wrote a letter to John von Neuman which
(06:43):
kicked off this quest to solve one of the biggest
questions in computer science, the P versus n P issue. Now,
who were these guys, but both were titans of the
twentieth century in terms of math, logic, and computers. Well.
Godal is probably most famous for his first incompleteness theorem,
and this states that any adequate um axiomatizeable theory that means,
(07:06):
a theory that's based on self evident but unprovable proofs,
is incomplete or inconsistent. Yeah. Girdle's whole incompleteness theorem set. Yeah,
A couple of his incompleteness theorems essentially amount to the
idea that any mathematical system that makes sense will have
some statements that are true yet impossible to prove. It's
(07:27):
sort of the idea that you can't ever know everything
about a self consistent system. Yeah, and the the The
implication here, according to theoretical physicist and mathematician Freeman Dyson,
who has is also quite a giant in the field,
is that mathematics is inexhaustible, that no matter how many
problems we solve, will inevitably encounter more unsolvable problems within
(07:49):
the existing rules. I take comfort in that measure of futility. Yeah,
but there's also John von Neuman, the recipient of the letter.
And von Neuman. I don't know what you've heard about him,
but I'd say he's often considered one of the most
intelligent people who ever lived that we know about at least,
and so maybe we call him a mathematician and a physicist,
(08:10):
but he made contributions to numerous fields. He was a
modern Da Vinci kind of you know, a polymath, and
and that includes computer science, for example, the von Neuman
architecture in the history of computer design, which is basically
it's a way of controlling the interaction between processing operations
the CPU and the memory of a computer. And this
letter in nineteen fifty six from Girdle to von Neumann
(08:33):
started this process of looking into the question of whether
P does or does not equal in P. Now, like
I said, we're about to explain what all the terms
here mean. But I do want to note at the
outset of this explanation that you know, on this show
we always try to do our best to present our
subjects accurately, but then at the same time be understandable
(08:55):
to the average person. And this, this P versus in
P issue in complexity theory is probably the most difficult
and abstract subject I've ever tried to cover on a podcast.
So we'll have to do our best to explain the
issue and its implications without losing you in asphyxiating clouds
of abstraction. Yeah, I mean, basically, the House of Works
UH mission overall is to demystify your science and UH
(09:19):
topics like this can be a bit difficult because you
don't want to through the explanation just mystify it even
more for the average listener exactly right. So this is
necessarily going to involve a lot of simplified versions of principles.
We won't be able to go down uh and explore
all of the complex details behind these principles, but we
hope that you computer scientists and mathematicians out there will
(09:40):
not be too scandalized or think we're doing violence to
your subject. Uh. Anyway, here we go. So we we
got to start with the concept of algorithms. What what
is an algorithm? Well, I'd say an algorithm is a
self contained list of instructions to solve a problem. You've
got a goal, and then you make us step by
step list of things to do that gets you to
(10:03):
the goal. A common example within a computer program would
be a subroutine designed to sort a list of things.
That's an algorithm. Yeah, and you know, algorithms are something
we encounter on a just on a daily basis, especially online.
I mean Facebook, Google. Both of these depend on ever
changing algorithms to decide what you see and don't see
(10:25):
on your feeds and on your search results. Yeah, and
I think that's a great example of how complex algorithms
can get. You've got the simple sorting algorithm on one hand,
and then you've got the stuff that decides whether you
only see political articles you agree with or whether you
sometimes see stuff that's going to make you mad. So,
when you're designing algorithms in in a computer science arena,
(10:46):
or really to solve any problem, but we're mostly gonna
be talking about computer programs, you compare how much time
it takes to solve a problem with an algorithm, given
the scope of a problem. So this is usually expressed
in terms of inputs versus time. So I want to
give a quick example with sorting. Like I said, you say,
(11:07):
you're given a spreadsheet that includes a list of all
the James Bond movies that exist currently in a random order,
and you've got to write a computer program that sorts
all of those lists of James Bond movie titles into
a list in the order they came out. How would
you do that? Now, there are a lot of ways
you actually could approach the problem, and that they don't
(11:29):
all take the same amount of time. Some are much
more efficient than others. Here's one example. You could create
an algorithm that goes like this. Step one, rearrange the
entire list at random. Step two, check each movie in
the list to see if it came out before the
next movie in the list. If the answer is yes,
all the way down the line, then the list is
(11:50):
sorted correctly and you're done. If not, start over and
rearrange it entirely randomly. Now, given enough time and a
small enough data set, this algorithm will if eventually finished
by blind luck. It is just brute force burning through
computer resources wastefully in order to eventually solve the problem
by blind block. But there are also much more efficient
(12:13):
ways you could go about it. For example, you could
go down the list comparing each movie to the next,
and if the second movie came out before the first,
you switch their order on the list and then go
on like that. Uh, and then you do that until
the list is sorted. But some problems are inherently a
lot harder than others, and there aren't any algorithmic shortcuts
(12:34):
like that that we know about. We don't know of
any easy way to solve them. The only thing we
know how to do is do that stupid brute force
method where you just wastefully burned through computer resources until
it's solved by time and force. And in fact, I'd
like to make a comparison here in the you know,
the efficient algorithm versus brute force methods, to what you
(12:58):
might see in animals in the wild using intelligence to
solve a problem. So like, if you're hunting another animal,
you could use a brute force method of just running
after the animal until it is tired or until your
muscles have allowed you to catch it, and then killing
it with the strength of your muscles. That's sort of
the brute force method. Or you could set a trap,
(13:20):
or you could build a weapon that these are shortcuts
that make the process of hunting a lot more efficient.
Now here's where we get to our main terms in
this discussion, P and n P. P is going to
stand for polynomial time and n P stands for nondeterministic
polynomial time. You don't really need to remember that for
the purpose of this discussion, because we're gonna make it
(13:42):
a lot simpler. Yeah, I mean, this is one of
the problems with the topic, is that like just the
word just this the the the basic idea here of
P and MP there, it's so dry and unrelatable. But
allow us to explain. Yeah, okay, So the real difference
has to do with um processes of solving problems on
a determinus dick Turing machine, which is equivalent to the
(14:02):
kind of computer you'd be using right now, you know,
any device you have, versus a hypothetical nondeterministic machine, which
in theory you could say works by magically guessing the
answers to questions and then just checking to see if
the magic guess is correct. But, like we said, we
don't want to get too bogged down in all those details.
So here's the simplified version. P is a set of
(14:25):
all problems that can be solved by an algorithm quickly
or easily or efficiently. This is the easy. The list
of easy problems in computer science. N P, on the
other hand, stands for answers that can be easily checked
by a computer once you have them, but they can't
necessarily be solved easily. Yeah. So it's difficult to place
(14:48):
this in a non mathematical context. But one way I
like to think about this is in terms of written reviews,
for for albums, for for for musical albums. Um, because
a good a good review, a good music review is
is difficult to write, uh, and hard to find and
hard to find. Yeah, Like in my own experience, you
(15:08):
often find I mean, I I write many reviews of
stuff of stuff from time to time, and that alone
is challenging enough for me. But but yeah, when you
even when you're looking out of the major publications, uh, yeah,
it's hard to find one that feels just right. It's Uh.
The average reader, though, can can swiftly judge to what
extent they agree with the author, obviously, to what extent
(15:29):
the author is just blowing smoke. We've all read those
music reviews where you get the sense that the the
author is really using the music as an excuse to
sort of write his or her own poetry. Uh, they're
on the page as opposed actually describing what the music
is like. But but the reader knows. So the reader
can can can look at the material and either believe
(15:52):
them or you don't. Either you buy into their opinion
or you don't. Yeah, so you could. You don't have
the algorithm internally to efficiently right this piece of writing yourself,
but you know it when you see it exactly. Yeah,
it's kind of like pornography in that sens right. You
might not be able to define clearly the difference between
art and pornography, but you know it when you see it.
(16:14):
Once you have that answer certificate there, you can check
and by golly, it checks out. And I like that
because it also gives a whole new meaning to the
P and to the MP and H. Now, so there
are a couple of other terms that matter there. There's
MP hard, and this means that are problems that are
(16:34):
as hard as any other MP problem essentially. And then
there's also MP complete, which is a big issue in
this arena, and this is problems that are m P
and n P hard so you you can check the
answer once you have it in in a reasonable amount
of time, and their MP hard. Now, the interesting thing
about MP complete problems is that it has been proved
(16:57):
in the literature that if you have an algorithm that
and efficiently solve one MP complete problem, it can be
transposed to solve all of them. These problems reduced to
each other. So if you if you can solve one
MP complete problem in a reasonable amount of time, you
have found the master key. And this in the universe
(17:19):
kind of shrinks in response to this. So a classic
example of an MP problem is the prime factorization problem
that we use in encryption on the Internet. Again, we
don't want you to get lost too much here, so
here's the simple version with smaller numbers than usual. Let's
say I just throw out a random number, and let's
say it's a number of I don't know what's a
(17:41):
good one skulls in a pile. So let's say I
give you a number. Let's say there are seven hundred
and twenty one thousand, four hundred twenty one skulls in
a pile. It is now I tell you this number
is the product of two prime numbers of skulls in
a pile, but I don't tell you what they are. Now,
(18:03):
how could you figure out what those two prime numbers
of skulls in a pile are? For a computer with
numbers this small, this wouldn't be all that big a deal.
But we're we're gonna have to extrapolate too much bigger numbers.
But for you, this would be really annoying to figure out, right,
because there's no simple efficient way to do it. You'd
(18:24):
pretty much have to get out a huge list of
all the prime numbers between zero and seven thousand, four
hundred one and start trying multiplying them together to see
if they give you the right answer. Yeah, and in
this situation, I imagine it's like the opening scenes of Terminator,
and I'm probably already pretty distracted by the Pyramids of
(18:46):
Bone and the Hunter Killer, the Hunter Killers exactly, I'm
not gonna have time for all this prime number nuns. Now,
since we've solved p equals in p at this point,
they don't have rubber skin anymore. They figured out how
to how to get through the problem to make the
bio or suits. So yeah, you're you're in a real
rush here. But anyway, back to the problem. Yeah, there's
(19:07):
just no fast, simple, easy way to solve this. And
if you use numbers large enough, this type of problem
is excruciatingly slow, even for computers to conquer by brute force.
But let's say I told you the two prime numbers
are seven hundred and fifty seven and nine hundred and
fifty three piles skulls in a pile. It would be
(19:29):
trivially easy for you to check and see if that's
the correct solution. You just have to multiply them and
see if you get the right answer, and that takes
almost no time at all. And in fact, I'd really
only need to tell you one of the numbers because
you already know what they're supposed to multiply too, so
you could just divide that by the one number. So
here's an example. This is a problem that if you're
going to try to solve it starting with no information,
(19:51):
it's just going to take you ages. It's going to
be impossible. But if you already know a selected answer
to test, you can I can see if that answer
is right. Yeah, I mean this brings to mind. Uh,
it's a bit like trying to crack a four number
code on a simple combination lock, right, And I'm talking
about a human doing this, not a computer. So it
(20:12):
would take me as a human quite a while to
test out all ten thousand possible solutions, but no time
at all to check a solution that someone else had
provided me. So you know, I'd be there all day
just putting in each one of those ten thousand solutions.
But but I can easily put in you know, uh,
thirty three sixty six and see if that is correct.
(20:33):
You found a really interesting request for help on this subject,
and you, oh, yeah, yeah, there was because I wanted
to check to make sure that my math was right
on how many possible combinations. I was pretty sure it
was the ten by ten by ten by ten thing.
But I I did one of those searchers to just
see people asking math questions online, and I found one where, um,
(20:54):
this user apparently had a combination lock or it maybe
it was like a contract actor's box, you know, like
at a house we have a real estate agent. Yeah,
and she says it's like a thirty dollar box. So
she didn't want to just have it, you know, cut
into and ruin it in order to get the keys out.
She wanted to, but she didn't know what the combo was,
so she wanted to just enter all the possible combinations
(21:18):
to get it. And here's the here's the caveat though
she knows that no number was used, uh more than once,
and that cut it down significantly, just just more than
five thousand. Yeah, just was like five thousand forty or something. Yeah.
And and the person who supply the answer on this forum,
they included a list of all of them for her convenience.
(21:39):
So um, I and I don't know how that came out.
I wonder if she then took that list and just painstakingly, uh,
spent the time to try each one out, or if
she decided, you know, actually that inputting all those numbers
is not worth the thirty dollars that I would save
by keeping the box intact. That sounds like a fun saturday,
you know, on the porch in front of the box
(21:59):
with the case a beer. Hopefully it's nice weather. But anyway,
so yeah, this is problems that can potentially be brutally
hard to solve, but they're easy to check once you
have a certificate of the answer. Another classic and often
(22:20):
cited example of an MP complete problem is the traveling
salesman problem. Now I think something is exciting because now
we have something with more of an anthropomorphic name. It
seems to imply a scenario. It's like the Infinity Hotel. Well,
I want to change it up and I want to
call I want to call this the nationwide infection problem.
So imagine that you are the vanguard of an alien
(22:42):
species that has come to Earth and you want to
land in a country, you say the United States, and
infect at least one person in every township and municipality
in this country with one of your larvae. But you've
got limited time to do it. A k. You know,
no Dilly dalian around. So what you're looking for is
(23:04):
a route that you can plan out on your alien
equivalent of Google Maps directions or or you know, your
Apple Directions device that will tell you how to go
to every single city and township in the country, only
one time each in the shortest route possible. Okay, that's
not easy. If you just had four or five cities,
(23:25):
this wouldn't be such a big deal for a computer
to figure out. Once you start adding hundreds or thousands
of cities, how is it going to figure this out?
The only way we know of is back to brute force.
It could try one method, so well, you go to
city A, and then city B, and then city C
and then D and go all the way around the
(23:45):
country and see how long that takes. And then it
could try again with first city B and then A,
and then the same from there and then so you
end up getting these exponentially multiplying combinations there. It is
just going to take massive amounts of time and computing
power to figure out what is actually the shortest trip. Now,
(24:07):
you might already see an issue with including this problem
within in P and actually reade an interesting blog post
by somebody writing for for IBM about how, under certain
conditions this problem actually isn't in P depending on how
you define what you're checking for. Like, if you're just
looking to check that a given route is a correct
solution it visits every city only once, uh, then it
(24:30):
is easy to check. You can check that very quickly.
This comes down to accurately defining the problem right exactly. Now,
if you're looking to check that it visits every city
only once under a certain mileage, that's also easy to check.
You just see that it visited every city once and
see how long it took. But if you're looking to
verify whether a solution is in fact the shortest of
(24:51):
all possible routes, that's not easy to check because you'd
still have you'd essentially have to do the entire brute
force method that way and compare or it to every
other possibility. All possible routes have to be to have
to be considered. So if if that's what you're going for,
it's not hard to solve, easy to check, It's hard
to solve and hard to check. But here's the big
(25:12):
problem with the with the P versus n P issue.
We know that P problems are a subset of MP problems,
But what if the subset is actually the same as
the set, Meaning what if all NP problems are actually
P problems? Meaning what if all problems where we can
(25:32):
check the answer are actually problems where we can solve
them efficiently. We just haven't figured out how to solve
them efficiently yet, Okay, or we haven't developed the here
the machines they can do it. Yeah, yeah, So is
that possible? And that's actually probably the single biggest open
question in computer science today? Is P equal or not
(25:55):
equal to n P? Are they or are they not
equivalent sets. Now, the obvious answer is no, right, that
seems intuitive, That seems that that seems to be the
answer that that feels most in keeping with our our
understanding of like the limits of human ability, the limits
of human knowledge, and just sort of the fabric of
(26:16):
our universe. Yeah, and so most computer scientists and mathematicians,
I think agree that the more likely answer to this
unsolved question is that P does not equal MP. I
found one pole that was taken. It was more than
ten years ago. I don't know if things have changed
much since then. But in two thousand two, the University
of Maryland computer scientist William I. Gas Arc did a
(26:37):
poll of colleagues in complexity theory and UH. And he
found the results. And so he found out of this
poll of colleagues, sixty one of his colleagues thought that
P did not equal MP. Nine thought that P did
equal MP. And some of those that said that said
they they said that basically just to be contrarian or
(26:58):
to continue encourage people to research the possibility. UH. And
then several other colleagues either offered no opinion or offered
UH sort of complex answers that weren't yes. Or no.
But so you can obviously see that the opinion that
P does equal MP, or the prediction that that will
be what's eventually proved, is the minority. It's not what
(27:22):
we would tend to think is the more likely possibility. Okay,
it's the more outsider consideration here. So let's assume for
a second that that is the case that one day
some amazing mathematician or computer scientists somebody comes along and
they figure out a way to prove that P does
not equal in P. Proof Proofs like this happen in uh,
(27:44):
in math and computer science all the time. You might
be wondering, how could that be proved, But people figure
out ways to demonstrate logically that something is true like this.
So let's say it's demonstrated that P does not equal MP.
What are the implications. Well, mostly, I'd say not much changes.
This is sort of the obvious conclusion. It's the one
that wouldn't surprise us. In other words, all of our
(28:07):
brute force problems remain brute force problems. UH. But if
this is the case, it would still be useful to know.
It would be useful that people wouldn't start floating into
the sky. The great old ones wouldn't come back. It
would just business is usual for most people. Yeah, so
we we'd have a proof, so people could stop trying
to solve it, and we'd be able to use the
fact that P is not equal to MP as an
(28:29):
assumption for other work in mathematics and computer science. So
we just move on with our lives basically essentially. But
here's where things get interesting. What would the implications be
if P does equal m P. Well, right off the
top of my head, of of course, what comes to
mind is the the the use of encryption that we've
(28:50):
already talked about, Like that's really like our most everyday
interaction with with the idea of of of P and MP. Yeah,
I mean, why is it not easy for me to
get into those photos you have on your phone, whatever
they are. Well, it's because it's because we use these
encryption methods. And almost all current encryption methods would be
(29:13):
subject to UH. They just depend on the fact that
you don't have, you know, tons of supercomputers and time
to sit around trying to brute force crack into people's junk.
But if you were able to reduce those problems to
UH to essentially easily solvable problems, problems that could be
solved in regular polynomial time. The P class then suddenly, yeah,
(29:37):
by by encryption essentially. I mean, we can't know for
sure exactly how big a deal this, uh, this would
be in terms of applied sciences and technology, but the
likely implication, uh seems to be that any job currently
hindered by the limits of brute force computation would be revolutionized.
So yeah, there's the there's the prime factorization issue that
(29:58):
that feeds into encryption. And the informal way of summing
this up is that you know, if, if if our
present methods of encryption and data security are like a
like a plastic diary lock on our information, every hacker
on Earth might have access to a pair of fourteen
inch bolt cutters if P equals n P. On the
other hand, and this would be a positive, it could
(30:19):
also mean that research projects that rely on brute force
computation could also potentially see huge leaps forward. For example,
one one that I saw, I've seen mentioned, and I've
read about before is protein folding simulation. Have you ever
read about this? Uh, yeah, a little bit. Um. I
think I tend to a discussion on on the topic
(30:40):
a few years back. Yeah, so this research, it involves
going through permutations of of different ways of folding proteins
in a computer simulation. And this research could help cure
diseases and treat medical conditions if we learned the right
things about the behavior of how protein molecules fold up
on one another and behave in the body. But simulating
(31:01):
all of these folding permutations is a brute force computing project.
So if this actually reduced to a p problem, we
might be able to hasten research that saves lives, maybe
cure cancer. Who knows. Okay, so we're already we're looking
at a world where maybe we have to go back
to using just normal mail instead of email. But on
(31:21):
the other hand, maybe we cure cancer. Or if people
i mean digital security maybe could still be a thing.
If people just come up with another method, we just
our current methods would would possibly become obsolete. Yeah, and
then the new method will be sealed envelope under your
back or a chest buried in your backyard. Yeah, that's
where you have to keep all You'd have to physically
(31:44):
meet up with everybody to trade information with an agree
on a password in person, you know, that would be interesting,
like trying to imagine a a digital civilization that suddenly
has to become a non digital civilization, but wants to
keep everything uh operating more or less as it did
when it moves digital. You know, like they still want
(32:05):
to use tender uh, but they can no longer use
a true digital version of it. What does that even
consist of? Oh wow, yeah, that's fascinating. But of course
the changes wouldn't just be in applied sciences and technology.
One of the interesting things about this is multiple experts
have commented that if we live in a P equals
(32:27):
in P universe, we have been sorely mistaken about what
reality is like. If this is the universe we inhabit,
in fact, it is quite different than we thought. And
one one thing I want to quote is by Scott Aaronson,
who offers this as quote a physical philosophical argument against
(32:48):
P equals in P, and he says, quote, if P
equals in P, then the world would be a profoundly
different place than we usually assume it to be. There
would be no special value for creative leaps, no fundamental
gap between solving a problem and recognizing the solution once
it's found everyone who could appreciate a symphony would be Mozart,
(33:11):
everyone who could follow a step by step argument would
be Gauss. Everyone who could recognize a good investment strategy
would be Warren Buffett. It's possible to put the point
in Darwinian terms. If this is the sort of universe
we inhabited, why wouldn't we already have evolved to take
advantage of it. That's a really interesting point. But at
(33:34):
the same time, so he's framing it in terms of it.
This is one among a list of arguments he gives
that P probably does not equal to. This seems to
be very much an argument in favor of their, of
their being no equality are right. But you could also
look at that look at it as an interesting comment
on how different the world would be from how we
(33:56):
assume it is if this were in fact the case.
And it's interesting to note that we shouldn't assume that
just because it doesn't feel like we live in the
P equals in P world, that P equals MP is
necessarily false. Our our intuitions about what's possible in the
math and problem solving space have turned out to be
very wrong in the past, and sometimes long standing problems
(34:17):
in math and computer science are solved by uh, solved.
They're solved or proved in ways that just seem extremely peculiar,
Yet you can't deny the result. I can't help but
circle back around to the earlier opinion that we mentioned
was attributed to Freeman Dyson that mathematics is inexhaustible. If
P equals MP, then the universe. Is the universe really inexhaustible? Yeah?
(34:43):
And uh? And if P equals MP, does that mean
that there is in a sense a universal algorithm out there? Uh?
I mean there there is a theory of everything within
our mathematical universes, as mass Max tech Mark argues in
mathematical universe theory that we mentioned earlier. Because the tech
Mark even go so far is to predict that a
mathematical proof for a theory of everything could eventually fit
(35:05):
on a T shirt. Well, I would kind of like
to the universe. Yeah, I mean that's an interesting thought
on its own. And tech Marks theories I I, as
I think I said earlier in this episode, I find
them very interesting, even if I'm not qualified enough to
know whether they're really rigorous physics. I read that book,
are our mathematical universe, and I found it amazingly stimulating.
(35:27):
You know, he talks about different levels of of multiverse
realities and what they each imply. Uh, and he gives
a very, at least to the lay person, a very
reasonable sounding explanation of how these are natural conclusions from
what we know about physics. But I do want to
use what you said as a sort of jumping off
point to take a broader view about the algorithmic nature
(35:50):
of reality. But first we're going to take a quick
break to hear from the sponsor of this episode. Everybody
in this day and age, you know the importance of
having a professional looking website. That's how you represent yourself
in the world at large. Come on, you can't just
have a Geo cities page hanging out there with all
your dancing baby gifts. It's it's and come on, that's right,
(36:13):
that's not gonna fly. The problem is, of course, most
of us, you know, we don't have the coding expertise
to go out and make one of these things. We
don't have the money to throw at some sort of
big fancy, big wig website designer. So what do you do?
You sign up for squarespace, is what you do. Because
squarespace they have the easy to use tools, the interface
that you need, all everything at your disposal to knock
(36:34):
out that professional looking website. Yeah, it'll look great and
it won't be scary. They take away all of the
gears and the creepiness of designing a website that make
it super intuitive, super easy. You have what you need
and you can make it yourself in no time. And hey,
if you want to use our offer code, you can
go to squarespace dot com and enter in mind blown
(36:54):
to get off your first purchase and a free domain
when you sign up today. So go check out square
airspace dot com special code mind blown and get started
making that awesome website. So whatever the solution to P
equals and P turns out to be, I think one
(37:15):
thing that's very interesting about it is just the idea
that this problem in computer science runs under the skin
of everything that exists. You know. It's it's not something
that people just made up. This is talking about a
fact about the universe that would be a fact about
the universe whether we were here to discuss it or not. Yeah,
(37:37):
I mean there's a certain amount of it's difficult kind
of to get to get outside of the mirror language
of the situation when we're talking about problem solving, because
we can't help but think about a human mind trying
to solve a problem. But in a sense, problem solving
takes place not only the human level, it takes place
that at at at at the animal level, as you know,
(37:59):
as this particular entity is trying to navigate a world
of fixed and moving objects, generally to acquire some gold,
to acquire food or or a mate. Uh, you could
even you could probably even extrapolated as far to say
to say that that an object obeying gravity is kind
of engaging in a sort of non mental problem solving
(38:22):
in a way, in in a limited way. Um, I
guess what I'm just trying to drive home here is
that when we continue to talk about problem solving here,
it's like trying not to think about it as much
within in the human realm, because it is we're about
to see it gets well outside of it, remove the
consciousness from it, and retain only the teleology exactly that
(38:44):
there there are there are steps towards a purpose, but
you don't have to know what the purpose is, and
you don't even have to realize you're taking steps right now.
A great example of this is the slime mold. So
slime molds don't have brains. They consists of a single
cell containing millions of nuclei and they form a network
of protoplasmic tubes to creep toward a food source along
(39:07):
the shortest path. That's essential here. Uh. It sends out
limbs to find food and when it finds us food source,
it spreads over, it secretes the digestive enzymes and has
its meal. When it doesn't, yeah, it's pretty it's pretty great.
Essentially the blob right, and when it doesn't find food,
then the limb you know, dies in retreats back. So
(39:28):
in this it creates a network for transporting nutrients and
chemicals for inter cellular communication. And that the method allows
them to perform such feats and this is generally and
this in lab environments. Uh, such feats as solving a maze,
like a straight up maze that you would put a
mouse in, as well as when presented with a miniaturized
(39:49):
earth environment, Uh, they can they can recreate some of
the great trade routes um of the world, of some
of the great highway systems. They can model cancer growth. Um,
let me go to a little detail about the silk
road thing, and this is this gets into exactly what
we're talking earlier about an algorithm attempting to to plot
(40:11):
a course, right and having to hit all those stuffs
the salesman problem that we're discussing earlier. Okay, So back
into computer scientist Andre Adamantski from the University of the
West of England. He took a globe. Okay, and you
can do this at home probably, I guess, if you
have access to the materials. He took a globe and
(40:31):
he coated it with auger all right, this, of course
is the stuff in a petri dish that you know
bacteria grows up. Yeah. Uh and then he um. And
then what he did is he removed uh, the augur
from the areas over the ocean, so it's just covering
the continents and the land at this point. And then
he placed oat flakes at the locations of twenty four
(40:52):
different major cities on the globe, so that's a food source. Okay.
Then he introduced the slime mold. Alright. He did this
thirty different times. In each time the slime mold conquered
the world in a slightly different way, establishing trade routes
between the various oats cities. Yeah, and it's uh there
their pictures out there. This is pretty remarkable, uh because
(41:14):
it it maybe a little bit scary because you see
these ten drils just spreading out all over the world.
It managed to plan out engineering projects that, of course
humans can only dream of right now, like Transatlantic bridges.
Obviously we're not going to do that. It wasn't, I didn't.
I don't think it was ever able to really conquer
the Pacific. Pacific was just too too uh too great
(41:34):
of a distance without Augur there for it to grow on. Uh.
But but it also managed to recreate the Silk Road
as well as the modern Asian Highway network, which consists
of about the eighty seven thousand miles of roads running
between thirty two countries. So it exactly it provides a
great example of uh, not a problem solving intelligence, but
(41:57):
an algorithmic problem solving organic system. Of course, this I
do think raises the specter of the question how do
you tell the difference between an algorithm and intelligence? Unless
you want to be anthropomorphic and say, well, intelligence is
consciousness and the ability to love and yeah, and then
we start gazing down that of this right, Yeah, yeah,
(42:19):
we get back to some of the problems we've discussed
in relation to AI in the past. How do you
know when you created it? If you can't really say
what it is, it becomes this this problem. We can't
even define the problem, So how can we come up
with the solution or check the solution? Yeah, And it's
funny that we were talking earlier about about sets that
sort of recursively consume one another. Is one set within
(42:42):
another set, but then the first set is the second
set is also in the first set. Now, we just
gave an example of how nature can be like an algorithm.
But you can also say that plenty of algorithms and
computer science have been essentially derived from nature. Yeah. Um,
And there's a great example of this with ants. So
(43:03):
ant colonies. We've discussed ance here in the podcast before
and I'm sure we'll cover them again in the future.
You know that they're complex societies, and we see plenty
of examples in which colonies accomplished complex tasks that exceed
the individual capacities of a single ant. Of course, so
they worked together and they're able to solve problems, and
this is mound mind. Yeah, exactly, it's the the the
(43:24):
the the emergent intelligence of the group, the swarm intelligence. Um.
This is a particular note to computer programming as though,
as we see how they're self organizing capacities and distributed
organization enable them to solve difficult optimization and distributed control problems. Okay,
So back in a Stanford study looked at how harvester
(43:46):
ants determine how many foragers to send out. Of course,
so they're sending out a rating party, right, Uh, which
is you know, more complex than than than you might think,
because you get down to the basic you know, how
many do you send out? You know, what's the way time? Uh?
And then they compared this to the manner in which
a search engine brings back search results. So specifically, yeah, specifically,
(44:10):
we're talking about transmission control protocol or TCP, which, if
you're like me, that's mostly something that you run into
when you have to adjust something on your your internet
situation at home. Yeah, but in anyway, it's a it's
(44:33):
essentially an algorithm that manages data congestion on the Internet.
So they they compared the two, right, and they combined
the two and they created the anternet. This is so
that's that's Internet, except instead of you have an ant UM.
So it's a TCP influenced algorithm that accurately matched ant
(44:55):
behavior in the experiment. So it's an example of ants
reaching the same place as our computer programming UM. So basically,
they created a TCP program that accurately predicted how the
ants were going to act. Yeah, we've definitely talked on
the other podcasts that I do with Jonathan Strickland and
Lauren Vogelbaum Forward Thinking. We talk about biomimetic robotics a
(45:17):
lot about ways that robots can be inspired by the
ways that animals move, especially in mobile robotics. You know,
how do you get a swarm of things to behave
as a group correctly? And I'd imagine that this would
be a very good example of how to control them. Yeah,
you see swarm organisms used in various AI programs. I
(45:37):
believe here Georgia Tech in Atlanta, they've used bees a lot.
Oh yeah, yeah. And more recently, a two thousand fourteen
study from Zurix Institute of Pharmaceutical Science has explored the
possibility of using ant algorithms to search for new composite
agents in the development of new pharmaceuticals. And this gets
down to the whole situation discussing earlier about do you
(45:58):
do you take a brute uh ranked approach to finding
out which connections amid all these possible connections are the
ideal ones to then test and explore. Um. So they've
looked into the possibility of using an ant based algorithm
to find though to do essentially, you know, magically guess
those uh those those the composite agents that that deserve
(46:21):
further examination. Well, you know, one thing these examples in
nature make me think about is an idea that really
intrigues me, and that's the question of whether evolution by
natural selection can itself be best interpreted as an algorithm,
because think about it, it's it's kind of an iterate
and test style algorithmic procedure. Let me give you a
(46:42):
list of steps. Step one, randomly introduce a change that
would be like a mutant allile into the genome. You
very one gene from the existing model, so you've random that.
That's step one. And then step two test against the
baseline performance rate of the standard allile in the environment
or you know, the individual steps here would be attempt
(47:03):
to copy. If copying succeeds, go to one or return
to the first step. If copying fails, return void. It's
almost like a computer program. Yeah, I think I think
there's a very strong case to be made there. I mean,
earlier I made that I said that gravity an object
of baying gravity and is it is in a way
(47:24):
kind of obeying a certain algorithm. It's kind of problem solving.
So this I think this FITSI bill as well. Yeah,
and I certainly didn't come up with this idea. I know,
I've read about it in the philosopher Daniel Dennett, who
advocated this point of view in this nine six book.
Darwin's dangerous idea was which was a lot about the
implications of evolution beyond just explaining the diversity of species
(47:47):
on Earth. Evolution is a sort of principle that extends
even beyond biology. But this universal driving force that that
drives design through the design space, and the way he
would explain it. But uh so, of course, not everybody
agrees with that interpretation, thinks that an algorithm is a
(48:07):
good way of thinking about evolution. But I've got another
follow up question that's kind of interesting to me, if
evolution is an algorithm, is it an efficient algorithm or
a brute force algorithm? Oh, now that's a good question.
I mean it seems to me kind of like it
would be a brute force algorithm, right, because you're you're
trying any number, it's you know, just brute force combinatrix.
(48:29):
You're trying something. Here's a pair of genes, here's an alleal.
Does that work? Now? Okay, throw in the trash. It
seems very wasteful. Yeah, here's a lizard with spots, here's
one without spots. Which one gets eaten? Which one continues?
That sounds like kind of a brute brute force You're
just like throwing out all the produce possible prototypes and
uh and seeing what then you see what happens. And
I think this would actually be one way of framing
(48:51):
the difference between the standard scientific materialist view of evolution,
which I think would probably be is best I can tell.
I bet that'd be the brute force method. And then
some types of believers in intelligent design. Right, So if
you are somebody who believes um, you you accept the
evidence for evolution and common descent, but you simply believe
(49:11):
the process was guided in one way or another. You
think aliens or a god or some other you know,
powerful supernatural or or other worldly technological force interfered with evolution,
maybe reached in to cause specific mutations to the terrestrial
genes space at key points. That sounds like that would
be optimizing the algorithm, right, like somebody's introducing artificial efficiency.
(49:37):
But then again, i'd i'd be interested in hearing from
the evolutionary biologists and geneticists sat there in the audience
on this one. Like, if you accept the idea that
natural selection is like an algorithm, is it a brute
force algorithm unless you go to the intelligent design hypothesis?
Or are there other ways of thinking of the algorithm
(49:57):
as in some way optimized by material cir substances. And
since you did mention god or the gods here would
the god in this scenario that Okay, so this is
a force coming from outside our universe, then perhaps in
this scenario our world is is a P does not
(50:18):
equal in P universe, but the realm of the gods
is a P equals in P universe. Uh Well, I
mean that's an interesting way of putting it, because they
can they can knock it out right there, Gods, they're
basically limitless. Well, it's infinite possibility, I mean, the whole
the realm of mathematics and logic is. In many ways,
(50:40):
it often signals to me the sort of underlying hint
of infinite possibilities but also infinite constraints. At the same time.
Mathematics is both infinite power and ultimate helplessness. You know,
it's the power to accomplish anything and the inevitability of
being thwarted and destroyed by processes beyond your control. Uh,
(51:01):
it just sort of makes everything good and bad possible. Well,
it sounds like you're talking about the gods again. It
could be yeah, all right, So there you have it.
P m P P versus m P P equals mp
P does not equal mp. Hopefully at this point you
have if you if you didn't know what any of
this stuff was about beforehand, you have a much better
(51:24):
grasp on the idea. You can at least realize why.
It is a topic that people continue to discuss and
even argue about. But if you want to get into
the actual details of of it, there are plenty of
good resources out there on the internet. If you are
a math and computer science and logic inclined to person
who has a good abstract mind for that kind of thing.
(51:44):
But either way, I do want to remind you to
always think about the algorithmic nature of the ground beneath
your feet and the laws that govern the way the
way everything around you works, the logic of reality. Is
there a problem solving process inherent to everything that's going
on around you all the time? I don't know. It's
(52:05):
it's a strange specter of an idea to keep behind
your head at all times. Yeah. Again, like when a
when like a walnut falls out of a tree, there
are certainly there's an there's an algorithm at play right
as to how exactly it's going to make it to
the ground, which branches is going to hit? I guess
that depends on your perspective. Is there is there a goal,
there is something happening or did something just happen? I
(52:29):
don't know, man, it's pretty far out. Well, let's not
get too much into weird stone or territory. Here at
the end, I do want to say, right here at
the end, if you are somebody who's involved in mathematics
or computer science and uh, and you would like to
write in to tell us about one of the one
of the more detailed or complex aspects of this that
we didn't get to. Like we said, we we gave
(52:51):
you the very simple version. Please right in and we'd
love to share your thoughts with the rest of you guys. Yeah,
and I'd also love to hear from anyone you know
who's read, uh some science fiction that definitely weighs in
on this. Um. You know, I was trying to think
of specific examples from N. N. Banks culture books because
the cour they have these minds, these ais that are
(53:12):
incredibly powerful, But for the life of me, I can't remember, uh,
exactly where they they weigh in in terms of the
or we're indeed, um Banks is universe there weighs in
on the on the the P and P spectrum. Hey.
But in the meantime, you want to check out this
and other pieces of content, head on over to stuff
(53:33):
to Blow your Mind dot com. That's the mothership. That's
where we have all the articles. That's where we have
blog posts, we have links out to social media, we
have some videos, uh, be sure to go there. Hey,
and if you listen to us on what iTunes, Spotify,
Google Play, however, you get your podcasts um it's possible
to do, so leave us a nice review there, give
(53:55):
us a little boost in the algorithm that ultimately uh
determines our eight. You can tweak that at that hour,
and you can reach out as a as an outside
force like a god, and shift things in our favor.
So invite you to do stuff. And as always, if
you'd like to get in touch with us, and we
really hope you do, you can email us and blow
the mind at how stuff works dot com for more
(54:26):
on this and thousands of other topics. Is it how
stuff works dot com.
Hey, welcome to Stuff to Blow Your Mind. My name
is Robert Lamb and I'm Joe McCormick, and it's Saturday.
What does that mean, Robert, What means it's time to
open the vault. It looks like it's already open, so
let's get in there. There's a lot of P in here.
There's also a lot of MP in here. Perhaps you
can explain this to everybody. Smooth transition, Robert, very smooth.
I like it. Uh. This is the episode on the
(00:28):
P versus MP problem, a classic fascinating vexing problem in
logic and math and computer science and uh. And in
this episode we tackle the question of what it actually
means to solve a problem. This originally aired on April twelve,
and we're bringing it back for you now, so we
hope you enjoy our exploration of the P versus MP problem.
(00:55):
Welcome to Stuff to Blow your Mind from how Stuff
Works dot com. Hey, welcome to Sceptable in your Mind.
My name is Robert Lamb and I'm Joe McCormick. And
today we're gonna be taking a look at the issue
in computer science. Uh. Funny enough, I'd say that's not
(01:18):
one of the science, as we dip into very frequently
on this podcast. Yes, and I mean, really, we should
probably just remind everyone to stick with us, trust us
on this one. Uh, don't be scared off by the
computer science thing. Don't be scared off by the P
versus MP thing. It's it's it's all gonna make a
type of sense at the end, hopefully. But I'm wondering
if maybe we should dip into computer science more often
(01:40):
because or at least wherever we can find a way
to make the contents of it reasonably concrete, because, let's
be honest, as we've discovered in researching this episode, it's
very abstract, very difficult, and a lot of times hard
to come up with ways of explaining that makes sense
just just talking about it without visual aids or watching
programs Exit Cute as an example. Yeah, it's definitely one
(02:02):
of those topics that it's a swimming pool of a
topic in which there is no gradual deepening from the
kitty area to the deep end. It's just shallow, and
at times it feels too shallow and then you're immediately
out of your depth. Yeah, but if you're thinking of
computer science, really does that fit with the show hold
on for a second, because I think it does. Um.
(02:24):
Computer science to me is a fascinating subject. Uh, and
it's not just limited to how computers work. So my
advice is, when you think about the idea of computer science,
forget the computer sitting in front of you. That's not
all it is. Computer science is really something more akin
to the philosophy of logic, understanding the the underlying sorcery
(02:47):
of how logic and math work in the universe we inhabit,
and especially the science of how problems are solved. And
certainly when you start bringing math into the equation here
as well, I mean you're talking we're talking about the
essentially the very fabric of the universe. We're talking about
either the fabric of the universe, either the way the
universe works, or this perfect creation that humans have come
(03:09):
up with that so accurately describes how the universe works,
and that is pretty mind blowing territory. Well, either way
you look at it, there is something mystical about about
the math that we walk on every day that you know,
that makes up the fabric and the logic math, the
math beneath our feet. You know, if you go with
the max Tech mark idea of the mathematical universe. Some
(03:30):
people don't like this idea because, like I don't understand
what that means, but at least it's a very intriguing idea.
I think his ideas that the underlying basis of all
reality not just as described by math, but is math,
and the universe is a mathematical object. But we're gonna
get back to this idea of problem solving because today
(03:51):
we want to focus on algorithms and on the inherent
logic of problem solving in our universe, with some attention
to a special example of one really interesting outstanding problem
in computer science, and that's the P versus n P issue.
If you've never heard of this before, don't worry. We'll
explain what the terms mean in in a simplified manner.
(04:12):
And uh I at this point also do want to
give a shout out to our listener Jim in New Jersey,
who has been encouraging me over email to tackle this
issue for a while despite all the challenges, and has
also sent some really helpful, uh really helpful guides and
explainers on some stuff. He he learned about this when
he was in graduate school. Yeah, indeed, and UH and
I think this is great too, because this episode is
(04:33):
coming on the heels of first of all, the Wicked
Problems episode that came out a few weeks ago, as
well as the more recent Cargo Cults episode which in
which we discuss some outside context problems a little bit
as well. So it's it's perfectly fitting that we would
discuss another problem. Well, what does it mean inherently to
(04:54):
solve a problem? If you get into the theory of
problem solving? What what what does this process look like? Well,
when it comes down just to the basics open and
this also kind of gets into the whole Wicked Problems
area of like, what's what's missing when you don't have, um,
you know, everything you need to solve a problem for
for a real problem, you have to be able to,
of course, do to find what the problem is. A
(05:16):
lot of a lot of attempts fail right there. Yeah,
you've got to You've got to be able to say
this is the thing you know and then you and
then you have to be able to measure your success
and check the solution. So you essentially have to be
able to say, hey, this is wrong because of X.
And then if you then figure out what x is
and see if the equation balances out. Um, it sounds
(05:38):
pretty simple. But like I said, as we discussed in
Wicked problems, that's uh, it can be very difficult to do,
especially in you know, the very complex social situations when
you're dealing with with certainly some of the larger problems
that we're going to talk about here, or even if
you want to go into the simplest level, well, I mean,
depending on what you would call simple. In fact, what
(05:58):
we're going to be getting into today is directly referred
to as complexity theory. Uh. So maybe it's not so simple,
but at least simple in terms of not involving uh
phenomena in the real world, but just math, just math
and logic and and true versus untrue and UH and algorithms.
So I think it's time to pull back the curtain
a little bit and reveal some of the deep weirdness
(06:21):
of the nature of algorithms and problem solving in our universe.
So let's look at this P versus MP problem. This
is something that comes from two of the great minds
of the twentieth century, Kurt Girdle and John von Neuman,
and in nineteen fifty six, Kurt Girdle, who's a mathematician
and logician, wrote a letter to John von Neuman which
(06:43):
kicked off this quest to solve one of the biggest
questions in computer science, the P versus n P issue. Now,
who were these guys, but both were titans of the
twentieth century in terms of math, logic, and computers. Well.
Godal is probably most famous for his first incompleteness theorem,
and this states that any adequate um axiomatizeable theory that means,
(07:06):
a theory that's based on self evident but unprovable proofs,
is incomplete or inconsistent. Yeah. Girdle's whole incompleteness theorem set. Yeah,
A couple of his incompleteness theorems essentially amount to the
idea that any mathematical system that makes sense will have
some statements that are true yet impossible to prove. It's
(07:27):
sort of the idea that you can't ever know everything
about a self consistent system. Yeah, and the the The
implication here, according to theoretical physicist and mathematician Freeman Dyson,
who has is also quite a giant in the field,
is that mathematics is inexhaustible, that no matter how many
problems we solve, will inevitably encounter more unsolvable problems within
(07:49):
the existing rules. I take comfort in that measure of futility. Yeah,
but there's also John von Neuman, the recipient of the letter.
And von Neuman. I don't know what you've heard about him,
but I'd say he's often considered one of the most
intelligent people who ever lived that we know about at least,
and so maybe we call him a mathematician and a physicist,
(08:10):
but he made contributions to numerous fields. He was a
modern Da Vinci kind of you know, a polymath, and
and that includes computer science, for example, the von Neuman
architecture in the history of computer design, which is basically
it's a way of controlling the interaction between processing operations
the CPU and the memory of a computer. And this
letter in nineteen fifty six from Girdle to von Neumann
(08:33):
started this process of looking into the question of whether
P does or does not equal in P. Now, like
I said, we're about to explain what all the terms
here mean. But I do want to note at the
outset of this explanation that you know, on this show
we always try to do our best to present our
subjects accurately, but then at the same time be understandable
(08:55):
to the average person. And this, this P versus in
P issue in complexity theory is probably the most difficult
and abstract subject I've ever tried to cover on a podcast.
So we'll have to do our best to explain the
issue and its implications without losing you in asphyxiating clouds
of abstraction. Yeah, I mean, basically, the House of Works
UH mission overall is to demystify your science and UH
(09:19):
topics like this can be a bit difficult because you
don't want to through the explanation just mystify it even
more for the average listener exactly right. So this is
necessarily going to involve a lot of simplified versions of principles.
We won't be able to go down uh and explore
all of the complex details behind these principles, but we
hope that you computer scientists and mathematicians out there will
(09:40):
not be too scandalized or think we're doing violence to
your subject. Uh. Anyway, here we go. So we we
got to start with the concept of algorithms. What what
is an algorithm? Well, I'd say an algorithm is a
self contained list of instructions to solve a problem. You've
got a goal, and then you make us step by
step list of things to do that gets you to
(10:03):
the goal. A common example within a computer program would
be a subroutine designed to sort a list of things.
That's an algorithm. Yeah, and you know, algorithms are something
we encounter on a just on a daily basis, especially online.
I mean Facebook, Google. Both of these depend on ever
changing algorithms to decide what you see and don't see
(10:25):
on your feeds and on your search results. Yeah, and
I think that's a great example of how complex algorithms
can get. You've got the simple sorting algorithm on one hand,
and then you've got the stuff that decides whether you
only see political articles you agree with or whether you
sometimes see stuff that's going to make you mad. So,
when you're designing algorithms in in a computer science arena,
(10:46):
or really to solve any problem, but we're mostly gonna
be talking about computer programs, you compare how much time
it takes to solve a problem with an algorithm, given
the scope of a problem. So this is usually expressed
in terms of inputs versus time. So I want to
give a quick example with sorting. Like I said, you say,
(11:07):
you're given a spreadsheet that includes a list of all
the James Bond movies that exist currently in a random order,
and you've got to write a computer program that sorts
all of those lists of James Bond movie titles into
a list in the order they came out. How would
you do that? Now, there are a lot of ways
you actually could approach the problem, and that they don't
(11:29):
all take the same amount of time. Some are much
more efficient than others. Here's one example. You could create
an algorithm that goes like this. Step one, rearrange the
entire list at random. Step two, check each movie in
the list to see if it came out before the
next movie in the list. If the answer is yes,
all the way down the line, then the list is
(11:50):
sorted correctly and you're done. If not, start over and
rearrange it entirely randomly. Now, given enough time and a
small enough data set, this algorithm will if eventually finished
by blind luck. It is just brute force burning through
computer resources wastefully in order to eventually solve the problem
by blind block. But there are also much more efficient
(12:13):
ways you could go about it. For example, you could
go down the list comparing each movie to the next,
and if the second movie came out before the first,
you switch their order on the list and then go
on like that. Uh, and then you do that until
the list is sorted. But some problems are inherently a
lot harder than others, and there aren't any algorithmic shortcuts
(12:34):
like that that we know about. We don't know of
any easy way to solve them. The only thing we
know how to do is do that stupid brute force
method where you just wastefully burned through computer resources until
it's solved by time and force. And in fact, I'd
like to make a comparison here in the you know,
the efficient algorithm versus brute force methods, to what you
(12:58):
might see in animals in the wild using intelligence to
solve a problem. So like, if you're hunting another animal,
you could use a brute force method of just running
after the animal until it is tired or until your
muscles have allowed you to catch it, and then killing
it with the strength of your muscles. That's sort of
the brute force method. Or you could set a trap,
(13:20):
or you could build a weapon that these are shortcuts
that make the process of hunting a lot more efficient.
Now here's where we get to our main terms in
this discussion, P and n P. P is going to
stand for polynomial time and n P stands for nondeterministic
polynomial time. You don't really need to remember that for
the purpose of this discussion, because we're gonna make it
(13:42):
a lot simpler. Yeah, I mean, this is one of
the problems with the topic, is that like just the
word just this the the the basic idea here of
P and MP there, it's so dry and unrelatable. But
allow us to explain. Yeah, okay, So the real difference
has to do with um processes of solving problems on
a determinus dick Turing machine, which is equivalent to the
(14:02):
kind of computer you'd be using right now, you know,
any device you have, versus a hypothetical nondeterministic machine, which
in theory you could say works by magically guessing the
answers to questions and then just checking to see if
the magic guess is correct. But, like we said, we
don't want to get too bogged down in all those details.
So here's the simplified version. P is a set of
(14:25):
all problems that can be solved by an algorithm quickly
or easily or efficiently. This is the easy. The list
of easy problems in computer science. N P, on the
other hand, stands for answers that can be easily checked
by a computer once you have them, but they can't
necessarily be solved easily. Yeah. So it's difficult to place
(14:48):
this in a non mathematical context. But one way I
like to think about this is in terms of written reviews,
for for albums, for for for musical albums. Um, because
a good a good review, a good music review is
is difficult to write, uh, and hard to find and
hard to find. Yeah, Like in my own experience, you
(15:08):
often find I mean, I I write many reviews of
stuff of stuff from time to time, and that alone
is challenging enough for me. But but yeah, when you
even when you're looking out of the major publications, uh, yeah,
it's hard to find one that feels just right. It's Uh.
The average reader, though, can can swiftly judge to what
extent they agree with the author, obviously, to what extent
(15:29):
the author is just blowing smoke. We've all read those
music reviews where you get the sense that the the
author is really using the music as an excuse to
sort of write his or her own poetry. Uh, they're
on the page as opposed actually describing what the music
is like. But but the reader knows. So the reader
can can can look at the material and either believe
(15:52):
them or you don't. Either you buy into their opinion
or you don't. Yeah, so you could. You don't have
the algorithm internally to efficiently right this piece of writing yourself,
but you know it when you see it exactly. Yeah,
it's kind of like pornography in that sens right. You
might not be able to define clearly the difference between
art and pornography, but you know it when you see it.
(16:14):
Once you have that answer certificate there, you can check
and by golly, it checks out. And I like that
because it also gives a whole new meaning to the
P and to the MP and H. Now, so there
are a couple of other terms that matter there. There's
MP hard, and this means that are problems that are
(16:34):
as hard as any other MP problem essentially. And then
there's also MP complete, which is a big issue in
this arena, and this is problems that are m P
and n P hard so you you can check the
answer once you have it in in a reasonable amount
of time, and their MP hard. Now, the interesting thing
about MP complete problems is that it has been proved
(16:57):
in the literature that if you have an algorithm that
and efficiently solve one MP complete problem, it can be
transposed to solve all of them. These problems reduced to
each other. So if you if you can solve one
MP complete problem in a reasonable amount of time, you
have found the master key. And this in the universe
(17:19):
kind of shrinks in response to this. So a classic
example of an MP problem is the prime factorization problem
that we use in encryption on the Internet. Again, we
don't want you to get lost too much here, so
here's the simple version with smaller numbers than usual. Let's
say I just throw out a random number, and let's
say it's a number of I don't know what's a
(17:41):
good one skulls in a pile. So let's say I
give you a number. Let's say there are seven hundred
and twenty one thousand, four hundred twenty one skulls in
a pile. It is now I tell you this number
is the product of two prime numbers of skulls in
a pile, but I don't tell you what they are. Now,
(18:03):
how could you figure out what those two prime numbers
of skulls in a pile are? For a computer with
numbers this small, this wouldn't be all that big a deal.
But we're we're gonna have to extrapolate too much bigger numbers.
But for you, this would be really annoying to figure out, right,
because there's no simple efficient way to do it. You'd
(18:24):
pretty much have to get out a huge list of
all the prime numbers between zero and seven thousand, four
hundred one and start trying multiplying them together to see
if they give you the right answer. Yeah, and in
this situation, I imagine it's like the opening scenes of Terminator,
and I'm probably already pretty distracted by the Pyramids of
(18:46):
Bone and the Hunter Killer, the Hunter Killers exactly, I'm
not gonna have time for all this prime number nuns. Now,
since we've solved p equals in p at this point,
they don't have rubber skin anymore. They figured out how
to how to get through the problem to make the
bio or suits. So yeah, you're you're in a real
rush here. But anyway, back to the problem. Yeah, there's
(19:07):
just no fast, simple, easy way to solve this. And
if you use numbers large enough, this type of problem
is excruciatingly slow, even for computers to conquer by brute force.
But let's say I told you the two prime numbers
are seven hundred and fifty seven and nine hundred and
fifty three piles skulls in a pile. It would be
(19:29):
trivially easy for you to check and see if that's
the correct solution. You just have to multiply them and
see if you get the right answer, and that takes
almost no time at all. And in fact, I'd really
only need to tell you one of the numbers because
you already know what they're supposed to multiply too, so
you could just divide that by the one number. So
here's an example. This is a problem that if you're
going to try to solve it starting with no information,
(19:51):
it's just going to take you ages. It's going to
be impossible. But if you already know a selected answer
to test, you can I can see if that answer
is right. Yeah, I mean this brings to mind. Uh,
it's a bit like trying to crack a four number
code on a simple combination lock, right, And I'm talking
about a human doing this, not a computer. So it
(20:12):
would take me as a human quite a while to
test out all ten thousand possible solutions, but no time
at all to check a solution that someone else had
provided me. So you know, I'd be there all day
just putting in each one of those ten thousand solutions.
But but I can easily put in you know, uh,
thirty three sixty six and see if that is correct.
(20:33):
You found a really interesting request for help on this subject,
and you, oh, yeah, yeah, there was because I wanted
to check to make sure that my math was right
on how many possible combinations. I was pretty sure it
was the ten by ten by ten by ten thing.
But I I did one of those searchers to just
see people asking math questions online, and I found one where, um,
(20:54):
this user apparently had a combination lock or it maybe
it was like a contract actor's box, you know, like
at a house we have a real estate agent. Yeah,
and she says it's like a thirty dollar box. So
she didn't want to just have it, you know, cut
into and ruin it in order to get the keys out.
She wanted to, but she didn't know what the combo was,
so she wanted to just enter all the possible combinations
(21:18):
to get it. And here's the here's the caveat though
she knows that no number was used, uh more than once,
and that cut it down significantly, just just more than
five thousand. Yeah, just was like five thousand forty or something. Yeah.
And and the person who supply the answer on this forum,
they included a list of all of them for her convenience.
(21:39):
So um, I and I don't know how that came out.
I wonder if she then took that list and just painstakingly, uh,
spent the time to try each one out, or if
she decided, you know, actually that inputting all those numbers
is not worth the thirty dollars that I would save
by keeping the box intact. That sounds like a fun saturday,
you know, on the porch in front of the box
(21:59):
with the case a beer. Hopefully it's nice weather. But anyway,
so yeah, this is problems that can potentially be brutally
hard to solve, but they're easy to check once you
have a certificate of the answer. Another classic and often
(22:20):
cited example of an MP complete problem is the traveling
salesman problem. Now I think something is exciting because now
we have something with more of an anthropomorphic name. It
seems to imply a scenario. It's like the Infinity Hotel. Well,
I want to change it up and I want to
call I want to call this the nationwide infection problem.
So imagine that you are the vanguard of an alien
(22:42):
species that has come to Earth and you want to
land in a country, you say the United States, and
infect at least one person in every township and municipality
in this country with one of your larvae. But you've
got limited time to do it. A k. You know,
no Dilly dalian around. So what you're looking for is
(23:04):
a route that you can plan out on your alien
equivalent of Google Maps directions or or you know, your
Apple Directions device that will tell you how to go
to every single city and township in the country, only
one time each in the shortest route possible. Okay, that's
not easy. If you just had four or five cities,
(23:25):
this wouldn't be such a big deal for a computer
to figure out. Once you start adding hundreds or thousands
of cities, how is it going to figure this out?
The only way we know of is back to brute force.
It could try one method, so well, you go to
city A, and then city B, and then city C
and then D and go all the way around the
(23:45):
country and see how long that takes. And then it
could try again with first city B and then A,
and then the same from there and then so you
end up getting these exponentially multiplying combinations there. It is
just going to take massive amounts of time and computing
power to figure out what is actually the shortest trip. Now,
(24:07):
you might already see an issue with including this problem
within in P and actually reade an interesting blog post
by somebody writing for for IBM about how, under certain
conditions this problem actually isn't in P depending on how
you define what you're checking for. Like, if you're just
looking to check that a given route is a correct
solution it visits every city only once, uh, then it
(24:30):
is easy to check. You can check that very quickly.
This comes down to accurately defining the problem right exactly. Now,
if you're looking to check that it visits every city
only once under a certain mileage, that's also easy to check.
You just see that it visited every city once and
see how long it took. But if you're looking to
verify whether a solution is in fact the shortest of
(24:51):
all possible routes, that's not easy to check because you'd
still have you'd essentially have to do the entire brute
force method that way and compare or it to every
other possibility. All possible routes have to be to have
to be considered. So if if that's what you're going for,
it's not hard to solve, easy to check, It's hard
to solve and hard to check. But here's the big
(25:12):
problem with the with the P versus n P issue.
We know that P problems are a subset of MP problems,
But what if the subset is actually the same as
the set, Meaning what if all NP problems are actually
P problems? Meaning what if all problems where we can
(25:32):
check the answer are actually problems where we can solve
them efficiently. We just haven't figured out how to solve
them efficiently yet, Okay, or we haven't developed the here
the machines they can do it. Yeah, yeah, So is
that possible? And that's actually probably the single biggest open
question in computer science today? Is P equal or not
(25:55):
equal to n P? Are they or are they not
equivalent sets. Now, the obvious answer is no, right, that
seems intuitive, That seems that that seems to be the
answer that that feels most in keeping with our our
understanding of like the limits of human ability, the limits
of human knowledge, and just sort of the fabric of
(26:16):
our universe. Yeah, and so most computer scientists and mathematicians,
I think agree that the more likely answer to this
unsolved question is that P does not equal MP. I
found one pole that was taken. It was more than
ten years ago. I don't know if things have changed
much since then. But in two thousand two, the University
of Maryland computer scientist William I. Gas Arc did a
(26:37):
poll of colleagues in complexity theory and UH. And he
found the results. And so he found out of this
poll of colleagues, sixty one of his colleagues thought that
P did not equal MP. Nine thought that P did
equal MP. And some of those that said that said
they they said that basically just to be contrarian or
(26:58):
to continue encourage people to research the possibility. UH. And
then several other colleagues either offered no opinion or offered
UH sort of complex answers that weren't yes. Or no.
But so you can obviously see that the opinion that
P does equal MP, or the prediction that that will
be what's eventually proved, is the minority. It's not what
(27:22):
we would tend to think is the more likely possibility. Okay,
it's the more outsider consideration here. So let's assume for
a second that that is the case that one day
some amazing mathematician or computer scientists somebody comes along and
they figure out a way to prove that P does
not equal in P. Proof Proofs like this happen in uh,
(27:44):
in math and computer science all the time. You might
be wondering, how could that be proved, But people figure
out ways to demonstrate logically that something is true like this.
So let's say it's demonstrated that P does not equal MP.
What are the implications. Well, mostly, I'd say not much changes.
This is sort of the obvious conclusion. It's the one
that wouldn't surprise us. In other words, all of our
(28:07):
brute force problems remain brute force problems. UH. But if
this is the case, it would still be useful to know.
It would be useful that people wouldn't start floating into
the sky. The great old ones wouldn't come back. It
would just business is usual for most people. Yeah, so
we we'd have a proof, so people could stop trying
to solve it, and we'd be able to use the
fact that P is not equal to MP as an
(28:29):
assumption for other work in mathematics and computer science. So
we just move on with our lives basically essentially. But
here's where things get interesting. What would the implications be
if P does equal m P. Well, right off the
top of my head, of of course, what comes to
mind is the the the use of encryption that we've
(28:50):
already talked about, Like that's really like our most everyday
interaction with with the idea of of of P and MP. Yeah,
I mean, why is it not easy for me to
get into those photos you have on your phone, whatever
they are. Well, it's because it's because we use these
encryption methods. And almost all current encryption methods would be
(29:13):
subject to UH. They just depend on the fact that
you don't have, you know, tons of supercomputers and time
to sit around trying to brute force crack into people's junk.
But if you were able to reduce those problems to
UH to essentially easily solvable problems, problems that could be
solved in regular polynomial time. The P class then suddenly, yeah,
(29:37):
by by encryption essentially. I mean, we can't know for
sure exactly how big a deal this, uh, this would
be in terms of applied sciences and technology, but the
likely implication, uh seems to be that any job currently
hindered by the limits of brute force computation would be revolutionized.
So yeah, there's the there's the prime factorization issue that
(29:58):
that feeds into encryption. And the informal way of summing
this up is that you know, if, if if our
present methods of encryption and data security are like a
like a plastic diary lock on our information, every hacker
on Earth might have access to a pair of fourteen
inch bolt cutters if P equals n P. On the
other hand, and this would be a positive, it could
(30:19):
also mean that research projects that rely on brute force
computation could also potentially see huge leaps forward. For example,
one one that I saw, I've seen mentioned, and I've
read about before is protein folding simulation. Have you ever
read about this? Uh, yeah, a little bit. Um. I
think I tend to a discussion on on the topic
(30:40):
a few years back. Yeah, so this research, it involves
going through permutations of of different ways of folding proteins
in a computer simulation. And this research could help cure
diseases and treat medical conditions if we learned the right
things about the behavior of how protein molecules fold up
on one another and behave in the body. But simulating
(31:01):
all of these folding permutations is a brute force computing project.
So if this actually reduced to a p problem, we
might be able to hasten research that saves lives, maybe
cure cancer. Who knows. Okay, so we're already we're looking
at a world where maybe we have to go back
to using just normal mail instead of email. But on
(31:21):
the other hand, maybe we cure cancer. Or if people
i mean digital security maybe could still be a thing.
If people just come up with another method, we just
our current methods would would possibly become obsolete. Yeah, and
then the new method will be sealed envelope under your
back or a chest buried in your backyard. Yeah, that's
where you have to keep all You'd have to physically
(31:44):
meet up with everybody to trade information with an agree
on a password in person, you know, that would be interesting,
like trying to imagine a a digital civilization that suddenly
has to become a non digital civilization, but wants to
keep everything uh operating more or less as it did
when it moves digital. You know, like they still want
(32:05):
to use tender uh, but they can no longer use
a true digital version of it. What does that even
consist of? Oh wow, yeah, that's fascinating. But of course
the changes wouldn't just be in applied sciences and technology.
One of the interesting things about this is multiple experts
have commented that if we live in a P equals
(32:27):
in P universe, we have been sorely mistaken about what
reality is like. If this is the universe we inhabit,
in fact, it is quite different than we thought. And
one one thing I want to quote is by Scott Aaronson,
who offers this as quote a physical philosophical argument against
(32:48):
P equals in P, and he says, quote, if P
equals in P, then the world would be a profoundly
different place than we usually assume it to be. There
would be no special value for creative leaps, no fundamental
gap between solving a problem and recognizing the solution once
it's found everyone who could appreciate a symphony would be Mozart,
(33:11):
everyone who could follow a step by step argument would
be Gauss. Everyone who could recognize a good investment strategy
would be Warren Buffett. It's possible to put the point
in Darwinian terms. If this is the sort of universe
we inhabited, why wouldn't we already have evolved to take
advantage of it. That's a really interesting point. But at
(33:34):
the same time, so he's framing it in terms of it.
This is one among a list of arguments he gives
that P probably does not equal to. This seems to
be very much an argument in favor of their, of
their being no equality are right. But you could also
look at that look at it as an interesting comment
on how different the world would be from how we
(33:56):
assume it is if this were in fact the case.
And it's interesting to note that we shouldn't assume that
just because it doesn't feel like we live in the
P equals in P world, that P equals MP is
necessarily false. Our our intuitions about what's possible in the
math and problem solving space have turned out to be
very wrong in the past, and sometimes long standing problems
(34:17):
in math and computer science are solved by uh, solved.
They're solved or proved in ways that just seem extremely peculiar,
Yet you can't deny the result. I can't help but
circle back around to the earlier opinion that we mentioned
was attributed to Freeman Dyson that mathematics is inexhaustible. If
P equals MP, then the universe. Is the universe really inexhaustible? Yeah?
(34:43):
And uh? And if P equals MP, does that mean
that there is in a sense a universal algorithm out there? Uh?
I mean there there is a theory of everything within
our mathematical universes, as mass Max tech Mark argues in
mathematical universe theory that we mentioned earlier. Because the tech
Mark even go so far is to predict that a
mathematical proof for a theory of everything could eventually fit
(35:05):
on a T shirt. Well, I would kind of like
to the universe. Yeah, I mean that's an interesting thought
on its own. And tech Marks theories I I, as
I think I said earlier in this episode, I find
them very interesting, even if I'm not qualified enough to
know whether they're really rigorous physics. I read that book,
are our mathematical universe, and I found it amazingly stimulating.
(35:27):
You know, he talks about different levels of of multiverse
realities and what they each imply. Uh, and he gives
a very, at least to the lay person, a very
reasonable sounding explanation of how these are natural conclusions from
what we know about physics. But I do want to
use what you said as a sort of jumping off
point to take a broader view about the algorithmic nature
(35:50):
of reality. But first we're going to take a quick
break to hear from the sponsor of this episode. Everybody
in this day and age, you know the importance of
having a professional looking website. That's how you represent yourself
in the world at large. Come on, you can't just
have a Geo cities page hanging out there with all
your dancing baby gifts. It's it's and come on, that's right,
(36:13):
that's not gonna fly. The problem is, of course, most
of us, you know, we don't have the coding expertise
to go out and make one of these things. We
don't have the money to throw at some sort of
big fancy, big wig website designer. So what do you do?
You sign up for squarespace, is what you do. Because
squarespace they have the easy to use tools, the interface
that you need, all everything at your disposal to knock
(36:34):
out that professional looking website. Yeah, it'll look great and
it won't be scary. They take away all of the
gears and the creepiness of designing a website that make
it super intuitive, super easy. You have what you need
and you can make it yourself in no time. And hey,
if you want to use our offer code, you can
go to squarespace dot com and enter in mind blown
(36:54):
to get off your first purchase and a free domain
when you sign up today. So go check out square
airspace dot com special code mind blown and get started
making that awesome website. So whatever the solution to P
equals and P turns out to be, I think one
(37:15):
thing that's very interesting about it is just the idea
that this problem in computer science runs under the skin
of everything that exists. You know. It's it's not something
that people just made up. This is talking about a
fact about the universe that would be a fact about
the universe whether we were here to discuss it or not. Yeah,
(37:37):
I mean there's a certain amount of it's difficult kind
of to get to get outside of the mirror language
of the situation when we're talking about problem solving, because
we can't help but think about a human mind trying
to solve a problem. But in a sense, problem solving
takes place not only the human level, it takes place
that at at at at the animal level, as you know,
(37:59):
as this particular entity is trying to navigate a world
of fixed and moving objects, generally to acquire some gold,
to acquire food or or a mate. Uh, you could
even you could probably even extrapolated as far to say
to say that that an object obeying gravity is kind
of engaging in a sort of non mental problem solving
(38:22):
in a way, in in a limited way. Um, I
guess what I'm just trying to drive home here is
that when we continue to talk about problem solving here,
it's like trying not to think about it as much
within in the human realm, because it is we're about
to see it gets well outside of it, remove the
consciousness from it, and retain only the teleology exactly that
(38:44):
there there are there are steps towards a purpose, but
you don't have to know what the purpose is, and
you don't even have to realize you're taking steps right now.
A great example of this is the slime mold. So
slime molds don't have brains. They consists of a single
cell containing millions of nuclei and they form a network
of protoplasmic tubes to creep toward a food source along
(39:07):
the shortest path. That's essential here. Uh. It sends out
limbs to find food and when it finds us food source,
it spreads over, it secretes the digestive enzymes and has
its meal. When it doesn't, yeah, it's pretty it's pretty great.
Essentially the blob right, and when it doesn't find food,
then the limb you know, dies in retreats back. So
(39:28):
in this it creates a network for transporting nutrients and
chemicals for inter cellular communication. And that the method allows
them to perform such feats and this is generally and
this in lab environments. Uh, such feats as solving a maze,
like a straight up maze that you would put a
mouse in, as well as when presented with a miniaturized
(39:49):
earth environment, Uh, they can they can recreate some of
the great trade routes um of the world, of some
of the great highway systems. They can model cancer growth. Um,
let me go to a little detail about the silk
road thing, and this is this gets into exactly what
we're talking earlier about an algorithm attempting to to plot
(40:11):
a course, right and having to hit all those stuffs
the salesman problem that we're discussing earlier. Okay, So back
into computer scientist Andre Adamantski from the University of the
West of England. He took a globe. Okay, and you
can do this at home probably, I guess, if you
have access to the materials. He took a globe and
(40:31):
he coated it with auger all right, this, of course
is the stuff in a petri dish that you know
bacteria grows up. Yeah. Uh and then he um. And
then what he did is he removed uh, the augur
from the areas over the ocean, so it's just covering
the continents and the land at this point. And then
he placed oat flakes at the locations of twenty four
(40:52):
different major cities on the globe, so that's a food source. Okay.
Then he introduced the slime mold. Alright. He did this
thirty different times. In each time the slime mold conquered
the world in a slightly different way, establishing trade routes
between the various oats cities. Yeah, and it's uh there
their pictures out there. This is pretty remarkable, uh because
(41:14):
it it maybe a little bit scary because you see
these ten drils just spreading out all over the world.
It managed to plan out engineering projects that, of course
humans can only dream of right now, like Transatlantic bridges.
Obviously we're not going to do that. It wasn't, I didn't.
I don't think it was ever able to really conquer
the Pacific. Pacific was just too too uh too great
(41:34):
of a distance without Augur there for it to grow on. Uh.
But but it also managed to recreate the Silk Road
as well as the modern Asian Highway network, which consists
of about the eighty seven thousand miles of roads running
between thirty two countries. So it exactly it provides a
great example of uh, not a problem solving intelligence, but
(41:57):
an algorithmic problem solving organic system. Of course, this I
do think raises the specter of the question how do
you tell the difference between an algorithm and intelligence? Unless
you want to be anthropomorphic and say, well, intelligence is
consciousness and the ability to love and yeah, and then
we start gazing down that of this right, Yeah, yeah,
(42:19):
we get back to some of the problems we've discussed
in relation to AI in the past. How do you
know when you created it? If you can't really say
what it is, it becomes this this problem. We can't
even define the problem, So how can we come up
with the solution or check the solution? Yeah, And it's
funny that we were talking earlier about about sets that
sort of recursively consume one another. Is one set within
(42:42):
another set, but then the first set is the second
set is also in the first set. Now, we just
gave an example of how nature can be like an algorithm.
But you can also say that plenty of algorithms and
computer science have been essentially derived from nature. Yeah. Um,
And there's a great example of this with ants. So
(43:03):
ant colonies. We've discussed ance here in the podcast before
and I'm sure we'll cover them again in the future.
You know that they're complex societies, and we see plenty
of examples in which colonies accomplished complex tasks that exceed
the individual capacities of a single ant. Of course, so
they worked together and they're able to solve problems, and
this is mound mind. Yeah, exactly, it's the the the
(43:24):
the the emergent intelligence of the group, the swarm intelligence. Um.
This is a particular note to computer programming as though,
as we see how they're self organizing capacities and distributed
organization enable them to solve difficult optimization and distributed control problems. Okay,
So back in a Stanford study looked at how harvester
(43:46):
ants determine how many foragers to send out. Of course,
so they're sending out a rating party, right, Uh, which
is you know, more complex than than than you might think,
because you get down to the basic you know, how
many do you send out? You know, what's the way time? Uh?
And then they compared this to the manner in which
a search engine brings back search results. So specifically, yeah, specifically,
(44:10):
we're talking about transmission control protocol or TCP, which, if
you're like me, that's mostly something that you run into
when you have to adjust something on your your internet
situation at home. Yeah, but in anyway, it's a it's
(44:33):
essentially an algorithm that manages data congestion on the Internet.
So they they compared the two, right, and they combined
the two and they created the anternet. This is so
that's that's Internet, except instead of you have an ant UM.
So it's a TCP influenced algorithm that accurately matched ant
(44:55):
behavior in the experiment. So it's an example of ants
reaching the same place as our computer programming UM. So basically,
they created a TCP program that accurately predicted how the
ants were going to act. Yeah, we've definitely talked on
the other podcasts that I do with Jonathan Strickland and
Lauren Vogelbaum Forward Thinking. We talk about biomimetic robotics a
(45:17):
lot about ways that robots can be inspired by the
ways that animals move, especially in mobile robotics. You know,
how do you get a swarm of things to behave
as a group correctly? And I'd imagine that this would
be a very good example of how to control them. Yeah,
you see swarm organisms used in various AI programs. I
(45:37):
believe here Georgia Tech in Atlanta, they've used bees a lot.
Oh yeah, yeah. And more recently, a two thousand fourteen
study from Zurix Institute of Pharmaceutical Science has explored the
possibility of using ant algorithms to search for new composite
agents in the development of new pharmaceuticals. And this gets
down to the whole situation discussing earlier about do you
(45:58):
do you take a brute uh ranked approach to finding
out which connections amid all these possible connections are the
ideal ones to then test and explore. Um. So they've
looked into the possibility of using an ant based algorithm
to find though to do essentially, you know, magically guess
those uh those those the composite agents that that deserve
(46:21):
further examination. Well, you know, one thing these examples in
nature make me think about is an idea that really
intrigues me, and that's the question of whether evolution by
natural selection can itself be best interpreted as an algorithm,
because think about it, it's it's kind of an iterate
and test style algorithmic procedure. Let me give you a
(46:42):
list of steps. Step one, randomly introduce a change that
would be like a mutant allile into the genome. You
very one gene from the existing model, so you've random that.
That's step one. And then step two test against the
baseline performance rate of the standard allile in the environment
or you know, the individual steps here would be attempt
(47:03):
to copy. If copying succeeds, go to one or return
to the first step. If copying fails, return void. It's
almost like a computer program. Yeah, I think I think
there's a very strong case to be made there. I mean,
earlier I made that I said that gravity an object
of baying gravity and is it is in a way
(47:24):
kind of obeying a certain algorithm. It's kind of problem solving.
So this I think this FITSI bill as well. Yeah,
and I certainly didn't come up with this idea. I know,
I've read about it in the philosopher Daniel Dennett, who
advocated this point of view in this nine six book.
Darwin's dangerous idea was which was a lot about the
implications of evolution beyond just explaining the diversity of species
(47:47):
on Earth. Evolution is a sort of principle that extends
even beyond biology. But this universal driving force that that
drives design through the design space, and the way he
would explain it. But uh so, of course, not everybody
agrees with that interpretation, thinks that an algorithm is a
(48:07):
good way of thinking about evolution. But I've got another
follow up question that's kind of interesting to me, if
evolution is an algorithm, is it an efficient algorithm or
a brute force algorithm? Oh, now that's a good question.
I mean it seems to me kind of like it
would be a brute force algorithm, right, because you're you're
trying any number, it's you know, just brute force combinatrix.
(48:29):
You're trying something. Here's a pair of genes, here's an alleal.
Does that work? Now? Okay, throw in the trash. It
seems very wasteful. Yeah, here's a lizard with spots, here's
one without spots. Which one gets eaten? Which one continues?
That sounds like kind of a brute brute force You're
just like throwing out all the produce possible prototypes and
uh and seeing what then you see what happens. And
I think this would actually be one way of framing
(48:51):
the difference between the standard scientific materialist view of evolution,
which I think would probably be is best I can tell.
I bet that'd be the brute force method. And then
some types of believers in intelligent design. Right, So if
you are somebody who believes um, you you accept the
evidence for evolution and common descent, but you simply believe
(49:11):
the process was guided in one way or another. You
think aliens or a god or some other you know,
powerful supernatural or or other worldly technological force interfered with evolution,
maybe reached in to cause specific mutations to the terrestrial
genes space at key points. That sounds like that would
be optimizing the algorithm, right, like somebody's introducing artificial efficiency.
(49:37):
But then again, i'd i'd be interested in hearing from
the evolutionary biologists and geneticists sat there in the audience
on this one. Like, if you accept the idea that
natural selection is like an algorithm, is it a brute
force algorithm unless you go to the intelligent design hypothesis?
Or are there other ways of thinking of the algorithm
(49:57):
as in some way optimized by material cir substances. And
since you did mention god or the gods here would
the god in this scenario that Okay, so this is
a force coming from outside our universe, then perhaps in
this scenario our world is is a P does not
(50:18):
equal in P universe, but the realm of the gods
is a P equals in P universe. Uh Well, I
mean that's an interesting way of putting it, because they
can they can knock it out right there, Gods, they're
basically limitless. Well, it's infinite possibility, I mean, the whole
the realm of mathematics and logic is. In many ways,
(50:40):
it often signals to me the sort of underlying hint
of infinite possibilities but also infinite constraints. At the same time.
Mathematics is both infinite power and ultimate helplessness. You know,
it's the power to accomplish anything and the inevitability of
being thwarted and destroyed by processes beyond your control. Uh,
(51:01):
it just sort of makes everything good and bad possible. Well,
it sounds like you're talking about the gods again. It
could be yeah, all right, So there you have it.
P m P P versus m P P equals mp
P does not equal mp. Hopefully at this point you
have if you if you didn't know what any of
this stuff was about beforehand, you have a much better
(51:24):
grasp on the idea. You can at least realize why.
It is a topic that people continue to discuss and
even argue about. But if you want to get into
the actual details of of it, there are plenty of
good resources out there on the internet. If you are
a math and computer science and logic inclined to person
who has a good abstract mind for that kind of thing.
(51:44):
But either way, I do want to remind you to
always think about the algorithmic nature of the ground beneath
your feet and the laws that govern the way the
way everything around you works, the logic of reality. Is
there a problem solving process inherent to everything that's going
on around you all the time? I don't know. It's
(52:05):
it's a strange specter of an idea to keep behind
your head at all times. Yeah. Again, like when a
when like a walnut falls out of a tree, there
are certainly there's an there's an algorithm at play right
as to how exactly it's going to make it to
the ground, which branches is going to hit? I guess
that depends on your perspective. Is there is there a goal,
there is something happening or did something just happen? I
(52:29):
don't know, man, it's pretty far out. Well, let's not
get too much into weird stone or territory. Here at
the end, I do want to say, right here at
the end, if you are somebody who's involved in mathematics
or computer science and uh, and you would like to
write in to tell us about one of the one
of the more detailed or complex aspects of this that
we didn't get to. Like we said, we we gave
(52:51):
you the very simple version. Please right in and we'd
love to share your thoughts with the rest of you guys. Yeah,
and I'd also love to hear from anyone you know
who's read, uh some science fiction that definitely weighs in
on this. Um. You know, I was trying to think
of specific examples from N. N. Banks culture books because
the cour they have these minds, these ais that are
(53:12):
incredibly powerful, But for the life of me, I can't remember, uh,
exactly where they they weigh in in terms of the
or we're indeed, um Banks is universe there weighs in
on the on the the P and P spectrum. Hey.
But in the meantime, you want to check out this
and other pieces of content, head on over to stuff
(53:33):
to Blow your Mind dot com. That's the mothership. That's
where we have all the articles. That's where we have
blog posts, we have links out to social media, we
have some videos, uh, be sure to go there. Hey,
and if you listen to us on what iTunes, Spotify,
Google Play, however, you get your podcasts um it's possible
to do, so leave us a nice review there, give
(53:55):
us a little boost in the algorithm that ultimately uh
determines our eight. You can tweak that at that hour,
and you can reach out as a as an outside
force like a god, and shift things in our favor.
So invite you to do stuff. And as always, if
you'd like to get in touch with us, and we
really hope you do, you can email us and blow
the mind at how stuff works dot com for more
(54:26):
on this and thousands of other topics. Is it how
stuff works dot com.
Stuff To Blow Your Mind News
Hosts And Creators
Robert Lamb
Joe McCormick
Popular Podcasts
United States of Kennedy
United States of Kennedy is a podcast about our cultural fascination with the Kennedy dynasty. Every week, hosts Lyra Smith and George Civeris go into one aspect of the Kennedy story.
Stuff You Should Know
If you've ever wanted to know about champagne, satanism, the Stonewall Uprising, chaos theory, LSD, El Nino, true crime and Rosa Parks, then look no further. Josh and Chuck have you covered.
Dateline NBC
Current and classic episodes, featuring compelling true-crime mysteries, powerful documentaries and in-depth investigations. Follow now to get the latest episodes of Dateline NBC completely free, or subscribe to Dateline Premium for ad-free listening and exclusive bonus content: DatelinePremium.com