Algorithms In The Blood: The P vs. NP Problem

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 and Joe 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.

Learn more about your ad-choices at https://www.iheartpodcastnetwork.com

See omnystudio.com/listener for privacy information.

Episode Transcript

Speaker 1 (00:03):
Welcome to Stuff to Blow your Mind from how Stop
works dot com. Hey, welcome to Spectable in your Mind.
My name is Robert Lamb and I'm Joe McCormick. And
today we're going to be taking a look at issue
in computer science. Uh funny enough, I'd say that's not

(00:25):
one of the sciences 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
NP thing. It's it's it's all gonna make a type
of sense at the end, hopefully. But I'm wondering if

(00:45):
maybe we should dip into computer science more often 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 execute

(01:07):
as an example. Yeah, it's definitely one 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, kind of computer science, really does
that fit with the show? Hold on for a second,

(01:30):
because I think it does. Um. 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

(01:51):
of logic, understanding the the underlying sorcery 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

(02:12):
fabric of the universe, either the way the universe works
or this perfect creation that humans have come 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 beneath the

(02:32):
math beneath our feet. You know, if you go with
the Max teg Mark idea of the mathematical universe that
some 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 it. His idea is that the
underlying basis of all reality not just as described by math,
but is math, and the universe is a mathematical object.

(02:55):
But we're gonna get back to this idea of problem
solving because today we want to focus on algori rhythms
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,

(03:16):
don't worry. We'll explain what the terms mean in a
simplified manner. 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

(03:38):
uh and I think this is great too because this
episode is coming on the heels of, first of all,
the Wicked Problems episode that came out of a few
weeks ago, as well as the more recent Cargo Cults
episode which in which we discuss outside context problems a
little bit as well. So it's it's perfectly fitting that
we would discuss another problem. Well, well, what does it

(04:00):
mean inherently to 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 course do to find what

(04:22):
the problem is a 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,

(04:45):
it sounds 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,

(05:06):
what 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

(05:27):
the deep weirdness 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

(05:49):
von Neuman which 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 heightens 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

(06:12):
axiomatizeable theory that means, a theory that's based on self
evident but unprovable proofs, is incomplete or inconsistent. Yeah, Girdle's
whole incompleteness theorem set. He had 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 sort of the idea

(06:35):
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 the existing rules. I take comfort

(06:59):
in that measure a few tility. 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,
but he made contributions to numerous fields. He was a

(07:20):
modern Da Vinci kind of you know, a polymath and so,
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 Neuman

(07:41):
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 the show
we always try to do our best to present our
subjects accurately but then at the same time be understandable

(08:02):
to the average person. And this, this P versus INP
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 that the house stuff
works mission overall is to demystify your science and UH

(08:27):
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

(08:48):
not be too scandalized or think we're doing violence to
your subject. Anyway, here we go. So we we've 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 a step by step

(09:08):
list of things to do that gets you to 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

(09:30):
what you see and don't see 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

(09:50):
algorithms in in a computer science arena, 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

(10:11):
example with sorting. Like I said, you say, 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

(10:31):
do that? Now, there are a lot of ways you
actually could approach the problem, and that they don't 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

(10:53):
movie in the list. If the answer is yes, all
the way down the line, then the list is 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 eventually finish by blind luck.
Is just brute force burning through computer resources wastefully in

(11:15):
order to eventually solve the problem by blind block. But
there are also much more efficient 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.

(11:35):
But some problems are inherently a lot harder than others,
and there aren't any algorithmic shortcuts 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

(11:57):
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 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

(12:17):
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, 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,

(12:42):
and in 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 a lot simpler. Yeah, I mean,
this is one of the problems with the topic is
that like just the word this, this the the the
basic idea here of P and n P. There, it's
so dry and unrelated, doble, But allow us to explain. Yeah, okay,

(13:02):
so the real difference has to do with um processes
of solving problems on a deterministic Turing machine, which is
equivalent to the 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

(13:24):
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 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,

(13:44):
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 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 you know, for
for musical albums, um. Because a good a good review,

(14:08):
a good music review is difficult to write, uh, and
hard to find and hard to find. Yeah, like in
my own experience you 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.

(14:29):
It's uh. The average reader, though, can can swiftly judge
to what extent they agree with the author, obviously, to
what extent 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 there on the page episodes actually just describing what

(14:52):
the music is like. But but the reader knows. So
the reader can can can look at the material and
you either believe in 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, and

(15:13):
that's it. It's right. You might not be able to
define clearly the difference between art and pornography, but you
know it when you see it. 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 NP.
And now, so there are a couple of other terms

(15:36):
that matter. There's MP hard, and this means that are
problems that are 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 m P hard. So you you can
check the answer once you have it in in a

(15:57):
reasonable amount of time, and they're in P hard. Now,
the interesting thing about MP complete problems is that it
has been proved in the literature that if you have
an algorithm that can 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

(16:18):
can solve one MP complete problem and a reasonable amount
of time, you have found the master key. And this
in the universe kind of shrinks. Yeah, 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,

(16:39):
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 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's a lot skulls, it is. Now,

(17:01):
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, 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,

(17:25):
this would be really annoying to figure out, right, Oh yes,
because there's no simple, efficient way to do it. You'd
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

(17:46):
this situation, I imagine it's like the opening scenes of Terminator,
And I'm probably already pretty distracted by the Pyramids of
Bone and the Hunter Killer. The Hunter Killers exactly how
I'm not gonna have time for all this prime number nuns. Now,
since we've solved the 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

(18:07):
bio org suits. So, yeah, you're you're in a real
rush here. But anyway, back to the problem. Yeah, there's
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

(18:30):
are seven hundred and fifty seven and nine hundred and
fifty three piles skulls in a pile. It would be
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 it takes
almost no time at all. And in fact, I really
only need to tell you one of the numbers because
you already know what they're supposed to multiply too, so

(18:51):
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,
it's just going to take ages. It's going to be impossible.
But if you already know a selected answer to test,
you can check and see if that answer is right. Yeah,
I mean this brings to mind. Uh it's a bit

(19:12):
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 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

(19:32):
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. You found a
really interesting request for help on this subject in 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

(19:53):
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,
this user apparently had a combination lock or it maybe
it was like a contractor's box, you know, like at
a house we had real estate agent. Yeah, and she
says it's like a thirty dollar box. So she didn't

(20:14):
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
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

(20:36):
than five thousand, yeah, just like or something. Yeah. And
and the person who supplied the answer on this forum,
they included a list of all of them for her convenience, so, um,
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

(20:59):
is not worth the thirty dollars that I would save
by keeping the box attacked. That sounds like a fun Saturday,
you know, on the porch in front of the box
with a case of 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

(21:21):
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 smply 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

(21:42):
are the vanguard of an alien species that has come
to Earth, and you want to land in a country,
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. Okay,
you know, no dilly dalian around. So what you're looking

(22:04):
for is 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,

(22:26):
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

(22:46):
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,

(23:08):
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,

(23:28):
it visits every city only once. Uh, then it is
easy to check. You can check that very quickly. All right,
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 checking.
Just see that it visited every city once and see
how long it took. But if you're looking to verify

(23:50):
whether a solution is in fact the shortest of all
possible routes, that's not easy to check because you'd still
have you'd essentially have to do the entire brute force
meth that that way and compare it to every other possibility.
All possible routes have to be 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

(24:11):
and hard to check. But here's the big 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?

(24:31):
Meaning what if all problems where we can 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 that can
do it. Yeah. Yeah, so is that possible? And that's
actually probably the single biggest open question in computer science today.

(24:54):
Is P equal or not equal to n P? Are
they or are they not? Equival valence 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 the limits
of human ability, the limits of human knowledge, and just

(25:16):
sort of the fabric of 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.

(25:37):
Guess Arc did a 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

(25:58):
to be contrarian or to continue encouraging 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.

(26:22):
It's not what we would tend to think is the
more likely possibility. Okay, it's the more outsider consideration here.
So it 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

(26:43):
Proofs like this happen in UH, 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

(27:05):
wouldn't surprise us. In other words, all of our 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 to people. Wouldn't start floating into
the sky, the great old ones, wouldn't come back, It
would just the business is usual for most people. Yeah,
So we we'd have a proof so people can stop

(27:25):
trying to solve it, and we'd be able to use
the fact that P is not equal to MP as
an 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 MP. Well, right off the

(27:47):
top of my head, of of course, what comes to
mind is the the the use of encryption that we've
already talked about. Like that's really like our most everyday
interaction with with the idea of of of P and NP. 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

(28:08):
encryption methods, and almost all current encryption methods would be
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

(28:30):
UH to essentially easily solvable problems, problems that could be
solved in regular polynomial time, the P class then suddenly, yeah,
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

(28:51):
hindered by the limits of brute force computation would be revolutionized.
So yeah, there's the there's the prime factorization issue that
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

(29:13):
on Earth might have access to a pair of fourteen
inch bolt cutters of the equals in p on the
other hand, and this would be a positive. It could
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

(29:34):
read about this? Uh? Yeah, a little bit. Um. I
think I tended a discussion on on the topic 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

(29:56):
about the behavior of how protein molecules fold up on
one another and be have in the body. But simulating
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

(30:16):
at a world where maybe we have to go back
to using just normal mail instead of email. But on
the other hand, and maybe we cure cantor 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

(30:39):
back or a chest buried in your backyard. Yeah, that's
where you have to keep all You'd have to physically
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

(31:00):
keep everything uh operating more or less as it did
when it lives digital, you know, like they still want
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.

(31:22):
One of the interesting things about this is multiple experts
have commented that if we live in a P equals
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,

(31:44):
who offers this as quote a physical philosophical argument against
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

(32:07):
it's found. Everyone who could appreciate a symphony would be Mozart,
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

(32:30):
advantage of it. That's a really interesting point. But at
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 and seems to be
This seems to be very much an argument in favor
of their, of their being no equality here, right, But

(32:51):
you could also look at that look at it as
an interesting comment on how different the world would be
from how we assume it is if this were in
fact case. And it's interesting to note that we shouldn't
assume that just because it doesn't feel like we live
in a P equals in P world, that P equals
np is necessarily false. Our our intuitions about what's possible

(33:12):
in the math and problem solving space have turned out
to be very wrong in the past, and sometimes long
standing problems 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

(33:32):
that we mentioned is attributed to Freeman Dyson that mathematics
is inexhaustible. If P equals MP in the universe, is
the universe really inexhaustible? And uh? And if P equals mp,
does that mean that there is, in a sense, that
a universal algorithm out there? Uh? I mean there there
is a theory of everything within our mathematical universes, as

(33:55):
math max tech Mark argues in mathematical universe theory that
we mentioned earlier. Because the tech Mark even go so
far as to predict that a mathematical proof for a
theory of everything could eventually fit on a T shirt. Well,
I would kind of like to do that the kind
of universe. Yeah, I mean, that's an interesting thought on
its own, and tech marks theories I I, as I

(34:15):
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 Our
Our Mathematical Universe, and I found it amazingly stimulating. You know.
He talks about different levels of of multiverse realities and
what they each imply. Uh, And he gives a very,

(34:37):
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 of reality.
But first we're going to take a quick break to
hear from the sponsor of this episode. Everybody in this

(35:02):
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 come on, that's right, 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,

(35:23):
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 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. They make it

(35:44):
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
to get twenty off your first purchase and a free
domain when you sign up today. So go check out
squarespace dot com special code mind blown and get started

(36:05):
making that awesome website. So whatever the solution to P
equals and P turns out to be. I think one
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

(36:28):
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,
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

(36:50):
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, at as
you know, as this particular entity is trying to navigate
a world of fixed and moving objects, generally to acquire
some goal, to acquire food or or a mate. Uh.
You could even you could probably even extrapolate it as

(37:12):
far to say to say that that an object obeying
gravity is kind of engaging in a sort of non
mental problem solving in a way, in in a limited way. Uh,
I guess 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

(37:34):
within in the human realm, because it is we're about
to see it gets well outside of it, remove the
consciousness from it, retain only the teleology exactly that 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

(37:57):
slime molds don't have brains. They consist of a single
cell containing millions of nuclei and they form a network
of protoplasmic tubes to creep toward a food source along
the shortest path. And that's essential here. Uh. It sends
out limbs to find food, and when it finds food source,
it spreads over, It secretes too digestive enzymes, and has

(38:19):
its meal. When it doesn't, yeah, it's pretty it's pretty great. Essentially,
have a blob, right and when it doesn't find food,
then the limb you know, dies in retreats back. So
in this it creates a network for transporting nutrients and chemicals,
for inter cellular communication and the method allows them to
perform such feats and this is generally and this is

(38:41):
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
earth environment. Uh, they can they can recreate some of
the great trade routes of the world, some of the
great highway systems. They can model cancer growth. Um. Let

(39:03):
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 a course
right and and having to hit all those stuffs the
salesman problem that we're discussing earlier. Okay, so back into
computer scientist Andre Adamanski from the University of the West

(39:24):
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 he
coated it with auger. All right, this, of course is
the stuff in a peat free dish that you know
bacteria grows up eat. Yeah. Uh and then he um.
And then what he did is he removed uh, the
auger from the areas over the ocean, so it's just

(39:47):
covering the continents and the land at this point. And
then he placed oat flakes at the locations of twenty
four different major cities on the globe, so that's a
food source. Okay. Then he introduced the slime mold. Alright.
He did this third any different times, and each time
the slime mold conquered the world in a slightly different way,
establishing trade routes between the various oats cities. Yeah, and

(40:10):
it's the picture their pictures out there. This is pretty remarkable,
uh because it and 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 don't. I don't think it was ever able

(40:31):
to really conquer the Pacific, be Pacific was just too
too uh too great of a distance without agur 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.

(40:52):
So it exactly it provides a great example of uh,
not a problem solving intelligence, but 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

(41:16):
to love and yeah, and then we start gazing down
that of this right, Yeah, you know, we get back
that 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

(41:37):
talking earlier about about sets that sort of recursively consume
one another. Is one set within 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

(41:57):
been essentially derived from nature. Um and yah, there's a
great example of this with ants. So ant colonies we've
discussed adnce 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

(42:19):
and they're able to solve problems. And this is mound mind. Yeah, exactly,
it's the the the 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

(42:44):
Stanford study looked at how harvester 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

(43:05):
then they compared this to the manner in which a
search engine brings back search results. So specifically, yeah, specifically,
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 but in anyway, it's a

(43:27):
it's 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. So that's that's Internet,
except instead of you, you have an ant um. So
it's a TCP influenced algorithm that accurately matched ant behavior

(43:50):
in the experiment. So it's an example of ants reaching
the same place as our computer programming UM. So basically
they created a tc PEE 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 biommetic robotics

(44:11):
a 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

(44:32):
believe here Georgia Tech in Atlanta, they've used bees a lot.
Oh yeah, yeah. And more recently, a two thousand fourteen
study from Zero's Institute of Pharmaceutical Sciences explore 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 in a situation discussing earlier about do

(44:52):
you do you take a brute uh strength 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 composite agents that that deserve

(45:16):
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

(45:37):
list of steps. Step one, randomly introduce a change that
would be like a mutant allele into the genome. You
very one gene from the existing model, so you've random that.
That's step one. 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 to copy.

(45:59):
If being 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
band gravity and is it is in a way kind
of obeying a certain algorithm. It's kind of problem solving.

(46:22):
So this I think this fits 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 book. Darwin's
dangerous idea was which was a lot about the implications
of evolution beyond just explaining the diversity of species on Earth.
Evolution is a sort of principle that extends even beyond biology.

(46:47):
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 ation thinks that an algorithm is a good way
of thinking about evolution. But I've got another follow up
question that's kind of interesting to me. If evolution is

(47:08):
an algorithm, is it an efficient algorithm or a brute
force algorithm? 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. You're trying something.
Here's a pair of genes, here's an alleal. Does that work? Now? Okay,

(47:29):
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 the
thing you see what happens, and I think this would
actually be one way of framing the difference between the
standard scientific materialist view of evolution, which I think would

(47:51):
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 are
somebody who believes um, you you accept the evidence for
evolution and common descent, but you simply believe the process
was guided in one way or another. You think aliens
or a god or some other you know, powerful supernatural

(48:13):
or otherworldly technological force interfered with evolution, maybe reached in
to cause specific mutations to the terrestrial gene space at
key points. That sounds like that would be optimizing the algorithm, right,
like somebody's introducing artificial efficiency. Yeah, but then again, i'd
i'd be interested in hearing from the evolutionary biologists and

(48:36):
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 as in some way
optimized by material circumstances. And since you did mention God

(48:58):
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 ped is not equal in the universe, but
the realm of the gods is a P equals in
p universe. Huh. Well, I mean that's an interesting way

(49:22):
of putting it. Like 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, 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

(49:46):
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. It just sort of makes everything
good and bad possible. But it sounds like you're talking
about the gods again. It could be Yeah, all right,
So there you have at p m p P versus

(50:08):
m P P equals m p 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 graph 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,

(50:30):
there are plenty of good resources out there on the
internet if you are a math and computer science and
logic inclined person who has a good abstract mind for
that kind of thing. 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

(50:50):
logic of reality. Uh, Is there a problem solving process
inherent to everything that's going on around you all the time?
I don't know. It's 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 certain there's an there's an algorithm

(51:10):
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 don't know, man, it's pretty far out. Well,
let's not get too much into weird stone or territory here.
And I do want to say right here at the end,

(51:32):
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 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

(51:54):
who's read some some science fiction that definitely weighs in
on this. Um. You know, I was trying to think
of sific examples from N. N. Banks culture books, because
the courent they have these minds, these aies that are
incredibly powerful. But for the life of me, I can't remember,
uh exactly where they they weigh in in terms of

(52:15):
the air We're indeed, um Banks is universe, their wigs
in on the on 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
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

(52:35):
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 podcast, um it, it's
possible to do. So, leave us a nice review there,
give us a little boost in the algorithm that ultimately,
uh determines our faith. You can tweet that at that

(52:56):
out of of and you can reach out as an
as an outside force like God and shift things in
our favor. So I invite you to do so. 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

(53:20):
for more onness and thousands of other topics. Is it
how stuff works dot com