Episode Transcript
[00:00:03] Speaker A: Computational complexity offers a lens which asks, you know, well, what are you trying to solve? Can you state your problem clearly in terms of an input that you're given and a question that you're trying to answer? I think that formalization is already a good thing to have because a lot of people in the broader culture, I think, don't think clearly enough about what it is that they want to achieve and what resources are they given to achieve it, and how will they know whether they've succeeded?
It's not clear to me that the brain at large is trying to solve mathematically well defined problems the way that theoretical computer science thinks about them.
I believe that when an intellectually honest person approaches a question that they should start out by being very agnostic about what kind of reasoning will be useful to help solve that question, and for that matter, also agnostic about what kind of question to ask. In my day job, I mostly work on well defined mathematical things. With the brain, I would have to start without very many preconceptions. Different fields have very different ideas about what constitutes a good question and what constitutes a a good answer to a question.
[00:01:31] Speaker B: This is brain inspired, Powered by the transmitter that's Christopher Moore. I'm Paul Middlebrooks and Chris is a professor at the Santa Fe Institute in New Mexico and he is a computation and computational complexity expert. He recently joined us in my complexity discussion group and he answered a bunch of our questions, but I wasn't done with him regarding what, if anything, computational complexity has to do with understanding how brains and minds work.
So that's why he's here today and we discuss a wide variety and winding path of topics related to AI computation, computational complexity, and cognition. I should say. Also we discussed this in the beginning, but he co wrote the textbook the Nature of Computation, which I link to in the show notes at BrandInspired Co podcast 240. Thanks for being here. I hope you enjoy our discussion. Here is Chris so this is the second time we've chatted now in over the past couple weeks. You were nice enough to join my little complexity discussion group and then I almost oh thanks. I mean it was great having you, but I almost I was worried I was going to take up your whole time during the discussion, but I had to shut up eventually and let other people jump in and just badger you with computational complexity questions.
So I asked you to come back and you were nice enough to come back and just be on the regular old podcast and today I'm going to badger you with cognition kinds of related questions and I know that you're not a cognitive scientist, but we're also going to talk about computational complexity. But let me just tell you sort of the main things that I'm. My kind of goals in this, in this discussion.
[00:03:24] Speaker A: I mean, we're all, we're all amateur cognitive scientists, right?
[00:03:27] Speaker B: Oh, no. Okay. Yeah. Good, good.
[00:03:30] Speaker A: I mean, aren't we all?
[00:03:33] Speaker B: Well, I started like, I'm on this, like bent on wondering about, you know, whether computation is the right metaphor for what brains do. And I'm skeptical of that. But, but the computational metaphor is just dominant in, in the neurosciences, especially.
One thing I want to, maybe one goal is to figure out whether computational complexity is even a relevant thing for understanding how brains or even artificial networks implement cognitive functions or functions in general.
But then I also want to think about the relative roles of computation and dynamics in explaining cognitive functions. And I'll explain more about that later. But so with those, those kind of in the background, first, I would like to learn about how you came to do what you do.
So some people, one could say that you wrote the book on the nature of computation, and perhaps that book title would be the Nature of Computation.
So you did write the book, the actual book of nature of computation, which you pointed.
[00:04:45] Speaker A: Available at all fine bookstores.
[00:04:47] Speaker B: It's a thousand pages.
[00:04:50] Speaker A: Yeah, well, some of them, you know, you can keep. If you use little Roman numerals for the preface, then you can keep the page count below a thousand. But yeah,
[00:05:02] Speaker B: so I was looking through it and I haven't read the whole thing yet, but whoa, what a.
The thing is just chock full of problems and examples that must have taken you a thousand years to put together.
[00:05:16] Speaker A: It took my friend Stephan Mertens and I only six years. So, you know, longer than going to college. But I learned a lot. And I mean, I think the joyful thing about writing a book like that is the sense when you succeed of taking material that people are often intimidated by and making it accessible.
Well, as opposed to what many academics do, which is the precise opposite of that.
So, you know, and for me, since I came to the field of computer science from the outside, I'm originally a physicist.
It was really trying to share the joy of learning this material and why we loved, why I fell in love with that field. And so, yeah, I mean, it has
[00:06:06] Speaker B: like a.
I'm sure people have told you this, it has kind of a Douglas Hofstadter kind of feel, not just because it's like a thick tome, but because it's kind of play and it's very agreeable. It sort of graciously invites the reader in to kind of play with you a little bit. And so it has that sort of tone. But in some of Hofstadter's work, I feel it can go a little bit on and on and on. So on the other side, that book, like, gets to the point really quickly as well. So it has, like, it does both somehow very well. I don't know if that was intentional
[00:06:41] Speaker A: in only a thousand pages, but it's been used as a text in a number of universities.
I mean, I think the first, for those who are currently intimidated by a thousand page books, I mean, the first 200 pages are actually quite palatable. Some of the latter half gets more.
A little bit more into technical material from quantum computing, from statistical physics, from the theory of Markov chain Monte Carlo algorithms, and so on.
I mean, we try to keep it accessible even then. But I'm so glad to hear you say that. I think in the preface we say that we tried to write with the.
What was it we mentioned Hofstadter, because I was very influenced by Godel Esher Bach. I think that book was really formative for a lot of people in my generation. And in fact, reading Godel Asher Bach when I was in college was partly what turned me towards computer science and computational complexity. Because for me, and I think for a lot of people then, it was the first time that I heard about Godel's incompleteness theorem, the first time I heard about Turing's Halting problem and some of these real touchstones, these paradoxical things that kind of, I think, draw a lot of people into this subject.
And of course, all the kind of high nerdy, high geek culture of Bach and Escher and all that was very attractive too. So I think in the preface of our book, we said we wanted to write with the playfulness of Gardner, because I also grew up on Martin Gardner and, and Hofstadter and the lyricism of Nabokov.
And we're sure that we failed on all counts. But anyway, sorry, I forgot.
[00:08:43] Speaker B: Your website says you love Nabokov. Nabokov, I suppose, is how you pronounce it.
[00:08:48] Speaker A: I think that's the Russian. Yeah, Anyway, whatever.
[00:08:52] Speaker B: Well, okay, so your background was physics. And by the way, I think this is the first time I've heard a computer science person say that they were turned on to computer science via Godel Escher, Bach, because a lot of computational neuroscientists cite that as the original inspiration for their becoming interested in the neurosciences. I Guess it has inspired multiple fields. Before we get into all the cognitive stuff. I mean, people know computational complexity because of the famous P versus NP problem, which you should say something about. But the Nature of Computation book that you wrote is in 2011.
And so that was kind of before whatever, 2000, the 2012 Imagenet big jump in accuracy in artificial neural networks and sort of before the rise of AI that we know it as today, large language models, et cetera.
[00:09:46] Speaker A: Right.
[00:09:47] Speaker B: And so there's kind of that question of how computational complexity has come along since then, but also just more broadly like what's been happening, what's the state of computational complexity these days relative to when you were writing in 2011, which took you six years and I imagine, I mean, you already had quantum computing in the book, so there's probably been some stuff there. But so just kind of broadly, what's the state of computational complexity right now?
[00:10:14] Speaker A: You know, it's important for people to understand that computational complexity is really fundamentally, it's a branch of mathematics.
And in fact, you know, it's something that if they had wanted to Gauss, or even the Greeks or the Babylonians or the Persians could have done if they wanted. In fact, there are little whispers of things like the fast Fourier transform in the works of Gauss, and there are little.
The word algorithm comes from the 14th century, if I recall geometer Al Khwarizmi, who was writing down recipes or procedures for solving algebraic and geometrical problems. And you know, in other words, algorithms which take a certain input and produce a certain output.
And you know, I think like all branches of mathematics, it is, it is a, it provides a formalism, a point of view which may or may not map well onto a given system in the real world. Right. And you started this conversation asking, you know, how much does this have to do with the brain? And I share some of your skepticism there.
And you know, as, and we talked a little bit about this in your discussion group.
Whether or not it is the right model to the right formalism to apply to a social or biological system or an AI or a market or you know, an ant colony or whatever it is, it's one of the, I like to say, lenses through which it's good to look through.
You know, the.
There is, you know, at the Santa Fe Institute we have, we're happy to be this very cross disciplinary institution.
And one of the great things you learn when you work with people from different scientific and intellectual cultures is there are different lenses for looking at the world. Like, if you like, I would Say that the physics lens is a lens where you look for simplicity, for elegance, things like conservation laws and symmetries, the things which let us understand elementary particles, even if it's much harder to understand larger things made out of elementary particles.
You know, the evolution lens is about, well, what selective pressures are things under and so on, and how does that make them change over time to be the way they are? The optimization lens, which I think is almost ubiquitous at the moment, especially in Silicon Valley, is. Well, surely there is one best solution, and the goal is to find it. Something which I would hate for people to apply to their diet or their parenting strategy, but it has leaked out into the culture to a large extent, right? There's one best way of doing things, and, and if you're not doing that, then you're living in sin.
And similarly, I would say that computational complexity offers a lens which asks, you know, well, what are you trying to solve?
You know, can, can you state your problem clearly in terms of an input that you're given and a question that you're trying to answer, whether that's the value of a certain function or whether it's, does a state of a certain quality exist according to some well defined objective function, or is it possible to satisfy all these constraints, or is it possible to get from here to there in less than a thousand miles, et cetera, et cetera.
And then I think that formalization is already a good thing to have because a lot of people in the broader culture, I think, don't think clearly enough about what it is that they want to achieve and what resources are they given to achieve it, and how will they know what, whether they've succeeded.
But it is also, you know, like any other lens, it brings some things into focus, it makes some things easier to see, and maybe obscures other things.
And so, for instance, the brain, I mean, it's not clear to me that the brain at large is trying to solve mathematically well defined problems the way that theoretical computer science thinks about them. And that's, that's okay. There might be, there might be individual modules that are, and moreover, there might be ways that the brain does things which could be, could offer new algorithmic ideas.
And there are a handful of computer scientists that are trying to think about that, like, what is a neural algorithm? And I'm not sure whether what they're doing would make sense to you as a neuroscientist, but it's sort of like, well, what if the quote steps of a neural algorithm are things like recruiting an additional population of neurons through synchronization, you know, sort of shifting attention, blah, blah, blah.
I would say that their work is at a very early stage. It's hard to tell whether it will pan out. But that's interesting too. So even if the brain is, at least in part algorithmic, the basic building blocks of its algorithms might be very different from the ones that we're used to in digital computers and, or gates and so on, for loops. And while loops, that might not be how the brain works.
So anyway, But I think the way that I talk to people in the larger world about computational complexity is to say, sometimes, even when we do have a well defined mathematical problem, we've all agreed, at least for the moment, on what we're trying to maximize or minimize, what the constraints are that we're trying to satisfy, what the variables are that we get to move around or choose to satisfy those constraints.
Even after we've done all that, some problems are still much harder than others.
And why is that so? The theory is all about drawing these qualitative distinctions between different problems based on their fundamental structure.
It's not about making computers faster.
The standard thing you see in the first chapter of every computational complexity textbook is, well, if the amount of effort it takes to solve a problem grows exponentially, like 2 to the n and your current computer can solve problems with n equals 100, your next year's computer, which is twice as fast, will be able to solve problems with 101 things instead of 100 whoop de do, because 2 to the 101 is twice as big as 2 to the 100.
Whereas if your algorithm grows only linearly, or say, quadratically, if the amount of time you need grows polynomially, as we say, with respect to the amount of data, the number of cities, the number of nodes in the network, the number of bits in the string, whatever it is, then the Moore's law no relation improvement in computational speed will help you out a lot.
I think that, at least at a metaphorical level, there are a lot of good ideas here, such as, if you have an astronomical number, a vast landscape of possible solutions to a problem, do you have to search the whole darn thing with an exhaustive search?
Will you even. Or is there a shortcut around that?
When you find a solution that works, will you even know that it works?
Or is even that hard even verifying a solution?
So this is what the P vs NP vs higher parts of the hierarchy are all about.
And I think that's. These are good questions for people who are trying to solve problems to think about.
[00:18:35] Speaker B: Well, I was going to say, does that mean computational complexity is all about bounds and limits and
[00:18:44] Speaker A: the,
[00:18:48] Speaker B: the least efficient, the most efficient algorithm that you can implement to solve a problem? I mean, so it puts it. Computational complexity has different classes like P and np, like you were just saying. But in some sense it's not about, like, in some sense you should say this because I'm going to fumble it. Right? So how is it not bound like. So it kind of puts the different kinds of computations into different categories based on their solvability or what it would take to solve them. And in that sense, it's sort of setting the upper. The limits of that categorized, that bound the categorizations of different kinds of computations. Sorry, Right.
[00:19:27] Speaker A: No, no, I think that's right on. I mean, I think we look for both lower limits and upper limits.
So for instance, if you have a problem and someone comes up with an algorithm, and let's say that you're thinking about time, we also think about memory and energy and communication and other things, but let's just say time.
If someone comes up with an algorithm that runs in N cubed time, for examples of size N, well, that puts an upper limit on its complexity. It means that it isn't worse than N cubed.
But there might be a cleverer algorithm. It might be only N squared, for instance.
On the other hand, we are also interested in lower bounds on the difficulty of a problem, but these are much harder to prove, right? Because how do you know that there isn't a clever algorithm out there that nobody's thought of yet?
This is why things like Turing's halting problem are so profound, right? I mean, when you first hear about, oh, well, can I tell whether this program will ever halt? Or many of the kind of versions of this in disguise that are not even obviously about computation, like, oh, here is a set of wooden tiles of different shapes. Can I cover an infinite plane with a pattern of these tiles? Right. That's also undecidable, right? But unless you're into cellular automata and a bunch of other stuff, you might not realize that that can be viewed as a question about Turing machines and computation in disguise.
So you might think, well, gee, I don't see yet how to solve this problem, but I don't see why I can't, right?
And then Turing comes along with this beautiful snake eating its own tail paradoxical all cretins are liars argument that shows that there really can be no program that can tell in finite time. If other programs could halt, because you could ask about itself but add a twist so then it halts if it doesn't halt, and doesn't halt if it does.
Contradiction. There's no such thing. I mean, that's an amazing kind of proof. And of course, if those glib words were all that Turing had done, we wouldn't be so impressed with him. But he had to build that proof out of hardware, as it were, out of machine language.
High level concepts like, oh, just, well, programs are both things that do things and they're text files of their source code. So just feed the program to itself as input, right?
I mean, from the point of view of mathematics before 1936 or so, the idea of feeding something to itself as input makes absolutely no sense, right? There are numbers like 7, there are functions like f of x is x squared.
There are other things like take the derivative of this function and get another function. But you can't feed things to themselves. What does that even mean?
But then Church with the lambda calculus, which turned into functional programming languages like Lisp and ML, and Turing with his Turing machine saying, hey, you can describe a Turing machine and write that on the tape of another Turing machine. And in another way Godel saying that there are mathematical statements using the integers addition and multiplication, which in some miraculous way talk about themselves.
I mean, that's amazing, right? And this is, of course, I'm kind of channeling Hofstadter here, because this amazing self reference is what Godel Escher, Bach was about.
Anyway. So way up there at the top of the complexity hierarchy, there is this amazing paradoxical proof that this problem is not solvable. There is a hard lower bound on the difficulty of this problem.
On the other hand, down in the world of P versus np.
So for your listeners, very briefly, right, so P stands for polynomial. It means these are problems that if you have an example of size N, a chessboard with N pieces on it or whatever, I think you kind of know intuitively, it's like the size of the email. I would need to send you that example of the problem.
You know, if a problem is np, we can solve it relatively efficiently, certainly without an exhaustive search through an astronomical number of possible solutions.
Whereas if it's in np, that is a much weaker guarantee. It means that if I show you the solution, or you trip over it, or God gives it to you in a dream, you can check the solution works.
So at least solutions are easy to check. That doesn't mean they're easy to find.
And my favorite example of this are things like, I mean, first of all, if you're trying to break a cryptogram, right, breaking crypto systems can be very hard. But when you succeed and you see the plaintext and it's a sentence in English or German about a U boat, you're pretty sure you've got it right. Right.
[00:25:11] Speaker B: Also a Turing throwback there as well.
[00:25:14] Speaker A: Exactly, yes.
Also an homage to Turing. So another example is if you are a puzzle hound like me, and you have these puzzles with lots of different pieces of different shapes and you're trying to fit them all together to form a cube, it might be hard to find the solution, but you know when you've got it right. So that's the characteristic of np. Whereas above that are even harder things. We're even telling that the solution works in some is hard to check.
So being able to check solutions and being able to find them feel like very different things.
And we believe that they're different things. So we believe that there are problems, so called NP complete problems, where yes, you can tell when you've found a solution, but there is no efficient way to find it.
[00:26:07] Speaker B: How do we believe that?
[00:26:09] Speaker A: Why do we believe that? We believe that because we feel that a lot of problems are like haystacks with needles in them, right? You have a big haystack. If you find, if you pick something out, you can prick your finger with it and tell whether it's a needle.
But if it is a Haystack of size 2 to the thousand, it's going to be very hard to find that needle or even tell if there is one.
And you know, unless you have some kind of algorithmic magnet that just sucks the needle out and then the problem would be in P. Right? Or if you have like an X ray that would let you like divide the haystack into two halves and just immediately check which one has a needle. And if it does, divide that into two quarters and divide that into two. 8. If you something like that, then the problem will be efficiently solvable.
But we really think that there are problems and they include things like telling whether an unsolved mathematical problem has a short proof. For instance, think about, you know, what is a formal proof? The whole point of a formal proof in mathematics is that you can check whether it's valid.
So that makes it a problem in np. I mean, just laboriously. And no one really enjoys doing this to do it axiomatically, which is why people are looking at, using automated systems like this, check that each line follows from all the previous lines according to the axioms. Okay? So that checking process is mechanical, but the process of finding proofs is anything but mechanical, which is why mathematicians have to be creative people, right? And you, you know, it's all blood, sweat and tears and doodling and, you know, staring at the ceiling at night and looking for counter examples. Failing. Thinking maybe it's true after all. Looking for proofs. Failing. Wondering if maybe there's a weaker version you can prove.
Finding a counter example to that, realizing you have to refine it further, going, you know, blah, blah, blah.
So this is why, of course, I'm very sad that for most people, their experience of mathematics is solve these 10 problems and you got eight check marks and two red X's. I mean, that's not how math is. Right, but do you have to do
[00:28:36] Speaker B: it that way to get to the fun beautiful part, though? Or could you start with the fun beautiful part? Sorry to interrupt. I just sort of.
[00:28:43] Speaker A: People have sort of voiced this is a great question.
I compare it like, what if you told children you may not write a poem until you can do spelling very, very well.
Right? Until you can diagram sentences very, very well? That would be hideous, Right? That would be child abuse.
So, I mean, it's also ironic because mathematics education is kind of based around speed and correctness, two things that many working mathematicians, including me, famously, don't have. Well, I don't have. I don't like these things, famously, but. Because I'm not famous. But the, I mean, a lot of the great mathematicians we admire are famous for making all kinds of mistakes all the time.
And, you know, I think among working mathematicians that someone is very fast and very clever. Of course we admire that. It's kind of like admiring Usain Bolt, like, he can run really fast. That's great. But what we admire more is something about depth or creativity, which is not something time limited.
And we could talk some more about this. I mean, we live in a culture which is focused so much now on productivity and so often that seems that we want to do more things more quickly, even if we're not doing them very well.
And I am one of those old fuddy duddies who worries about this. And I would rather, you know, I would rather write fewer papers and have them be better. I would rather, you know, I, I don't. I don't think maximizing the speed of things even. I mean, of course, there are things like medical research that I would like to go faster because we're saving lives.
If an asteroid were going to hit us in 60 days, I think we should all drop everything else and drink a lot of coffee and see what we can come up with.
But for a lot of other things, including law and justice, that shouldn't be something which we try to do too quickly.
I don't think making art or literature is something that is improved by trying to do it quickly.
[00:31:07] Speaker B: Well, I was thinking about the music analogy, right? Like we're. Because you're talking about the way that real mathematicians work, right? You're, you, you lay in bed, you think about it, it doesn't come to you. You think of an example and it, then you see that that example doesn't work when you check it against some background constraint or something. And then, you know, so you hear musicians all the. I'm sorry, this is still a tangent, but you know, it's a great doodle. They work and work, you know, they're, they're trying to compose, nothing's coming to them, and then all of a sudden it just kind of drops out, right? And, and they find the solution, which is their song, a good melody or whatever. And, but, but today we live in a world where you got to keep those hits cranking out, you know. So if you want to be known, if you want to make a living doing what you're doing, you got to crank it out. And so that you got another, you
[00:31:55] Speaker A: gotta, you gotta get another penny from Spotify, you know.
Yeah, that's right.
[00:32:00] Speaker B: That's right.
[00:32:00] Speaker A: You know, yeah. But it's interesting, the analogy with art and music I think is real because as I think we all know that a lot of creative people are among, you know, some of them, maybe not all, but they can be among some of the most self critical people we know.
They can be very hard on themselves, right? And not all of them, not all of them, some of them seem to be doing just fine, right? But you know, I mean, I think that to me, like, I think the act, the intellectual and creative activities that I admire the most are ones where there is no simple road to a solution or a proof or a good work of art or music.
You have to bring everything you've got to it. You have to explore, you have to pursue things that are sometimes dead ends.
You know, you have to bathe in the roller coaster of elation when you think you've got a tiger by the tail and then be crushed when it turns out not to work.
And so it's a combination of this sort of creativity and this grounding kind of feedback, like when you step back from the canvas and say, is This a good painting?
Or when you read a draft that you wrote and then you crumple it up and toss it across the room if you read it on paper.
People talk about foldable laptops. We need crumpleable laptops to bring that experience back. Right.
They are crumpleable if you work hard enough. Anyway, this is an even bigger tangent. I mean, I think of it almost like I think that people who are moral, thoughtful people sometimes rake themselves over the coals because they're thinking about, is the thing that I did or said to that person 20 years ago, was that right or wrong? Right. And that's that same kind of closure. If I were a more theological person, I would say, well, that's, you know, sort of sinners in the hands of an angry God or, you know, the fragment of the Holy Spirit in you or whatever, your inner moral compass, you know, you're really exposing yourself and asking, are. Are those actions? Really.
Were those right?
And I don't know. There's something. I've been thinking about writing some. It would probably be a crap essay, but I was thinking about writing something about this, about, you know, this sort of feedback process and.
And to continue the tangent, one more step, I think should spot a lot of.
[00:35:04] Speaker B: Please do write the essay.
[00:35:07] Speaker A: Well, okay.
I think this is exactly what a lot of us are frustrated about with the current state of AI, which is getting better, to be fair.
But last night, I was spending a lot of time with Gemini trying to confirm or just find out if there was literature about, because it is very good at searching academic literature, a pretty obscure mathematical problem that a postdoc at sfi, a really bright guy named Max Jurdi, and I are working on with another friend.
And it said, yes, this is in this paper by so and so. It's like, okay, can you give me a link? Well, it's in this journal.
So.
Which. Which. So I go to the. I can't find it. I come back and say, are you sure you have the title right? And it says, you're absolutely right to call me out. I owe you a and frank apology. I listened to that paper. It's like, okay, all right. You know, I mean, I make mistakes, too. And I've probably even made shit up once or twice when I wasn't sure what to say. But, you know, like, ground yourself. Create that internal loop.
It shouldn't take me saying, hey, I couldn't find that for you to say. Actually, sorry, I was making that up.
It's not really there.
And, you know, I think to be fair, AI is getting better at this. I know that people are building these multi agent systems where these agents check, those agents work and so on.
I think that for things where there is a ground truth which is not too hard to check, this is a solvable problem.
But it's irritating, it's still irritating that they can be so powerful and yet sometimes not close this loop, not close the loop of that feedback. That is what I'm saying, actually. True.
On the other hand, one more tangent perpendicular to that tangent two times, we're
[00:37:24] Speaker B: in high D space.
[00:37:25] Speaker A: Exactly three dimensions at least.
I mean, we all know that many human beings don't do this very much either.
I think we all know that we ourselves often don't. You know when you're at a cocktail party and some hip topic comes up like AI and you basically have a spiel ready to go and you're trying to impress the people that are there, you pull the string and you do your spiel and you could almost do it on automatic. And you're not, I could be doing this on automatic right now.
And I mean you're not really reflecting. You're not closing Hofstadter's loop of self awareness when you do this.
And we all know people who, when you ask them a question, sometimes they pause and say that's interesting. And they go back and think about it and sometimes people just steamroll over it and say, oh, but we're quite confident in this result.
Yeah, so maybe what AI can do. My favorite thing for AI to do, and I'm far from the first to say this, is hold up a kind of mirror to help us understand what our goals, what our aspirations for our behavior and our cognition is at our best.
Because many of our complaints about AI could also be leveled at much of human behavior and human utterances. It's like, ah, you're just spitting out a string of tokens. Yeah, mostly just like a lot of people do a lot of the time.
So you know, anyway, has AI got.
[00:39:05] Speaker B: So I'm going to bring us some somewhat back here on track. And has AI or deep learning neural networks, has it changed anything about computational complexity?
Questions or approaches or possibilities? Not, not in terms of using the AI to, to solve different problems like we were just talking about, but in terms of like a computing system or a, a method of solving things. Right. Which is kind of different than like a classical computing approach.
[00:39:41] Speaker A: Right.
I'm going to glibly and perhaps controversially say no, but that's because.
Theoretical computer science, computational complexity has A particularly rigid notion, for the most part, of what it means to solve a problem. And we talked about this in your discussion group too.
So traditionally there are exceptions. But traditionally, when a computer scientist says they have an algorithm which uses this much memory and takes that much time guaranteed, that guarantee means it works in every possible case, and in particular, it works in the worst possible case.
So even if a clever adversary, another theological term, comes along and cooks up the nastiest possible example of a problem, this algorithm will work on that just as quickly and with just as little effort as we promised.
And so, because that is what we mean classically when we say that, oh, I can solve this problem in polynomial time, that is, I can always solve it in polynomial time, then by that definition, if a problem is hard, that simply means that there exists hard examples, namely that, yeah, there are some examples that break your favorite algorithm, that break all of the fast algorithms.
However, that doesn't mean these examples are common. It doesn't mean you'll ever run across them.
And so there are lots of subtleties here, which I think.
So I think the success of AI on real world problems throws this definition of complexity and hardness into sharp relief. And to be fair, this debate is much older than modern AI. I mean, people who were doing automated logic were solving all sorts of undecidable problems, but solving them. I think Hofstadter in good. Alascher Bach. Bach gave the example of Fermat's last theorem, which now has been proved, but I think that came after the book was out.
So you take your famous math problem and you just write a little program that just tests bigger and bigger numbers and just looks for counterexamples. And if it finds a counterexample, it stops and hands you that counterexample.
But if the conjecture is true, it will never stop.
Therefore, if you could solve the halting problem, you could know instantly or well in finite time whether lots of unsolved mathematical questions are whether the answer is true or false, which is sort of a hint that we shouldn't be able to solve this problem in every possible case, because then mathematics would be over.
And that would be sad and also contradictory.
But of course, we solve lots of specific math problems all the time. And people who do automated software verification solve, in some sense, lots of halting problems all the time.
So lots of problems which are very hard in the computational complexity sense are easy most of the time.
[00:43:27] Speaker B: I started by asking you a few minutes ago how or whether artificial nets have affected computational complexity science at all. And you Said no, but then I sort of lost the thread of why?
[00:43:40] Speaker A: Sorry, the thread I was trying to give. The thread I was trying to give is that I think that artificial intelligence of a variety of architectures, including LLMs, is showing us that in real world, examples of problems, right? As opposed to worst case examples, there is tremendous structure that occurs there because of conscious design, because of evolution, you know, that like other forms of intelligence, including biological intelligence, these AIs can sink their teeth into and exploit. Right? So, you know, I think, I think at some level the most interesting thing about LLMs is they reveal the incredible depth of statistical structure in written text, right?
And you know, in some sense, and of course it's hard to mathematize what they do because they're deep networks and hard to interpret and so on, but they are at very least existence proofs that when you look at the long range structure of text, not just what we used to do, like adjacent words or triplets of words, n grams and so on, you can make tremendous progress in producing both plausible, even though sometimes false text, but also text which in some, you know, is sometimes true and correct in certain cases when there is a ground truth, you know, And I mean, of course I am still team human and of course I still feel like most of what they do is imitate style the same way. There are now AI systems that sound, at least to an untrained and to some fairly well trained listener, like something Bach could have wrote, right?
Something that seems to capture not just the short term Markovian structure of the measures and the melodies, like we can all do that, right? But something about the larger scale structure of a fugue, the kinds of structures that we're in awe of. Bach being able to hold in his mind that he could make a six part fugue where one of the themes is played upside down and backwards, right?
So we know that Bach and other musicians and at some level writers and artists.
Swim in the waters of these very large scale structures or deep structures.
And for a long time we've had, you know, it's hard to talk about the structures mathematically, like what are they? How do you, how do you even concretize that idea? And LLMs are at some level an existence proof that you can, right?
My, my pet belief is that a few years from now there are going to be a zillion different architectures out there.
We're going to feel like any reasonably flexible architecture with any sufficient amount of processing power thrown at it will be able to do all these things.
And that Ultimately, what we're learning about is what is the structure of the world? What is the structure of scenes with trees and dogs that let both us and AI understand them and caption them and predict what will happen? What is the structure of text or music that lets composers and listeners and AIs at some level grasp it? I think that would be an interesting.
That would be a very satisfying thing to have happen to bring this to
[00:47:54] Speaker B: the heart of some of the fundamentals of computational complexity. Right. So we're talking now about, I don't know if you can frame that structure, especially in let's say, a Bach sort of way, where let's say Bach produces this fugue and somehow has the structure in mind. That act of creation is not just about the structure of the world as it exists. It's some generative sort of process with some other constraints. And I don't. Is that, does that fall under the realm of a quote unquote problem? Because computation requires a problem and specific inputs and a solution. Right? So I don't know. Is a fugue a solution to anything?
[00:48:40] Speaker A: Yeah, that's interesting.
I mean, I think that a fugue and parts of fugues are solutions to problems which the composer has chosen.
Right. I suppose if I'm the King of Prussia and I say, I demand you make me a six part fugue based on this theme, that's a problem.
Happily, that's not how most of this works, I hope.
I mean, I think, you know, the wonderful thing, and this goes back to mathematics as well, right.
You know, I think what I really want school children and everyone else to understand is if you grow up and want to be a mathematician, you get to make up the problems.
Right?
It's not about.
Here is a question. Give me the right answer. You get to choose the questions.
You get to choose loony kinds of questions with new kinds of additional multiplication or division. You get to choose questions that are about drawing colored blobs on the paper instead of just the numbers. You get to invent new kinds of numbers. Right? I mean, that's the creative act of mathematics that people like me wish everyone understood and that our current educational system makes completely obscured.
Where am I going with this?
So the real world is full of natural images. The literary world is full of human generated text.
These things have structure, which is mostly kind of easy for us to understand and for AIs to understand.
And that's something to do with natural selection, in our case, with the nature. You know, our brains are co adapted to the world we live in. Our language is co adapted to each other's ability to speak and understand.
Then there are things like puzzle design which are like, I don't want it to be too easy.
That's a very interesting middle ground.
Then at the other end is adversarial design, the worst case, where an adversary is trying to make the hardest possible cryptosystem for you to crack, or trying to make an example of a problem which deliberately encodes some other really hard problem inside it.
And then there are lots of other things in between and in other directions, like what happens if you just make up a problem randomly.
There are beautiful phase transitions akin to the phase transitions in physics, where if you take your favorite NP complete problem. Some people have heard of a problem called Boolean satisfiability. You have a bunch of variables, they're Boolean variables, they can be true or false.
Then you have a bunch of constraints. One constraint might be, I want X to be true or Y to be false, or Z to be true. I want one of those things. At least one of those things. Some other constraint says, oh yeah, well, I want Z to be false or W to be true or S to be true.
Well, there's a little bit of attention there because one of these wanted Z to be true and the other wanted Z to be false. But luckily each had other ways to make them happy.
So there's still lots of solutions.
As you pile more and more of these constraints on and just demand more from your variables, at some point something's got to give, and at some point you can no longer satisfy the system.
And this is very much like the phase transitions in physics, where at a certain temperature water freezes, at a certain R0R naught, a certain level of reproduction and a disease will go from small outbreaks to a huge epidemic.
This is one of these classic things where the global behavior of a system changes suddenly when some parameter, the temperature, the effectiveness of the disease, or in this case the ratio of the number of constraints to the number of variables crosses some critical threshold.
And so the study of random problems, which are neither worst case nor real world, but they're sort of very interesting in their own right, has created this very exciting interdisciplinary collaboration between statistical physics and computer science, with some machine learning people thrown in, people from mathematics, random graph theory, combinatorics and so on.
And it turns out lots of other things happen which I think are metaphorically interesting pretty broadly, as you make the system.
When the system is not very constrained, solutions are really easy to find. And there's a sort of Huge cloud of them. And you can even move from one to another very easily.
You turn up the constraints.
Okay, there are still solutions, but now they're separated from each other into different clusters.
And if you're in one of these clusters, it's very hard to cross over to another cluster because to get from one to the other, you have to cross this valley where a lot of the constraints are unsatisfied.
It's kind of like you've put almost all of the luggage in your car, but you have to toss it all back out onto the driveway and totally rearrange it again and try it again. There isn't any small change you can make right again. That's kind of the hallmark of NP completeness.
And then at some point solutions exist. We can prove solutions exist, but we believe they become exponentially hard to find.
And this is a fascinating middle ground.
And it's very similar to what happens in spin glass theory in physics. So spin glass theory and the theory of glassy materials is a fascinating area of physics. It's the study of disordered materials.
So like a perfect crystal, pretty easy to understand.
I'm not saying it's trivial, but it's periodic. It's just the same pattern repeated over and over again. We have lots of mathematical tools for figuring things out about it.
But if you look at window glass, silicon dioxide, if you were to look at it at an atomic level, you would not see a crystal, which is interesting because its lowest energy state, its equilibrium state, the state it would really like to be in, is a perfect crystal.
That would be sort of the solution to the problem of minimizing its energy, minimizing the conflicts between the atoms.
But it never finds it. As you cool it down from molten glass, it always gets stuck in a jumbled state, a state that on an atomic level looks almost like a liquid.
And the reason is that, yes, this one would rather be aligned with its neighbor. They could form a little crystal, but to do that, it would have to disagree even more with the other neighbors. It would have to make things a lot worse in order to get better.
And, you know, if your listeners are kind of hanging out with complexity folks, they've all heard about this metaphor of the rugged landscape, the non convex landscape, where rather than one simple optimum like the peak of Mount Fuji that kind of dominates the world, if you start somewhere and start trying to improve things, you will get stuck at some local optimum where any small change makes it worse.
And yet there's a much better solution somewhere far off. But unfortunately, you have no idea where it is or in what direction to head to reach it.
And let's be honest, this feels like a lot of our social problems.
Yes, we all know this system is working poorly.
We all know it's crazy that it costs a billion dollars to build a mile of subway, but we all kind of know here. I'm starting to sound desire Kleinish. We all kind of know that there are lots of players who have built up lots of procedures, all with the best of intentions over time, and that as a result, the whole thing really sucks. And we can't build a damn thing even when we all agree it would be a really nice thing to have, and affordable housing, better subways, whatever.
And we all know that it is hard to solve these problems incrementally and sometimes we have to piss off a lot of people all at once.
[00:57:45] Speaker B: Anyway, isn't that what big deep neural networks are good at is derugifying the landscape so that there are lots of different paths to an optimal solution to whatever the problem is?
[00:58:03] Speaker A: Are they?
I mean, what I want to, what I would say is that most of the problems we actually solve them to. We ask them to solve are not that rugged in the first place. Right.
[00:58:16] Speaker B: Okay, well, so this is. Okay, maybe I'll transition then to this question because.
So I wanted to ask about neural nets and computational complexity because, you know, in computational complexity, you're generally asking about a specific problem or set of problems or like family of problems.
Unless maybe it's the randomized thing where you get these phase transitions that you were just talking about. But I mean, what are the chances that given.
So in artificial intelligence, the, the pinnacle is general AI or super intelligent AI, blah, blah, blah. But there's, but anyway, there's some generality to what you want to be able to do, and organisms exhibit that generality. Humans and, and many other organisms, especially with real neural networks. Networks, Right. Real, real brains. Right. There's. Is it possible that, like the, the structure of a neural network in this highly distributed network is somehow the optimal architecture for implementing such a general swath of solutions, just from a computational complexity point of view?
[00:59:33] Speaker A: So you're asking a couple of things at once, I think.
I mean, one thing I would say is that even artif. Even general intelligences, whatever they are, and I'm not even sure. Yeah, you know, we, we may or we may or not be general intelligences, but, you know, at the end of the day, we may only be good at certain things and.
[00:59:57] Speaker B: But we can do 12 different things. 12 different problems, we can solve different kinds of problems, Right.
[01:00:02] Speaker A: Whereas that's true.
[01:00:03] Speaker B: Right?
[01:00:03] Speaker A: Yeah.
And we are very good at building things to help us. Right. So when we want to do geometry, we start drawing in the sand with a stick.
And when we want to do arithmetic, we realize that Roman numerals are. Sorry. Or Arabic numerals are better than Roman ones.
And when we want to remember a lot of things and be able to look it up, we build libraries. So we're very good at augmenting the. You know, my friends Henry Farrell and Cosma Shalisi have a very nice piece out on AI as a cultural technology.
You know, a technology like the previous technologies we've built, which extends and amplifies our cognition. You know, if. If I really didn't have whiteboards or notepads, I could do a little math, but not very much, you know, not very much.
[01:00:53] Speaker B: It's like walking into a library and just saying, like, I want to learn about X and the library.
The right books come to you, except for the one that it hallucinates.
[01:01:02] Speaker A: And even that one might be pretty good if it would actually write it.
But so even general intelligence, I would say that because things like NP completeness and the fact that sometimes high dimensional landscapes are genuinely rugged, I would say that this is a difficulty for any form of intelligence that I can imagine.
I mean, there are times when you have been trying one strategy on a problem, you have a variety of reasons to think it's the best possible strategy.
You've been trying to improve it for a long time.
There's some completely different strategy out there, but it involves some approach that has really never crossed your mind.
And there's just no magic bullet, you know, there's just no way to just go and get that. You just have to hope that if you're creative and crazy enough and willing to go down rabbit holes and explore things that most people, including you, think are very unlikely to work, then you'll get lucky and find that other part of the strategy space.
And now you really have learned something and expanded your toolbox. But I mean, this issue of exploration versus exploitation, when should you keep looking where you are?
And when does it turn out to be under the lamppost? Right?
And when should you make a flashlight or go look at some other lamppost or start using sonar instead or whatever, Right?
And I mean, I think this is something which any intelligence would face. It doesn't matter whether it's made of meat or transistors, whether it's classical or quantum.
I mean, I think some Problems because of the structure of the problems.
The objective mathematical structure of the problems, not the subjective abilities of the solver.
What kind of brain they have or how fast they are, how much memory they have or how much compute they have. God, I hate that.
Could, how much computational power they have access to.
[01:03:20] Speaker B: You hate the word compute. How much compute they have? I don't know.
[01:03:23] Speaker A: What did Calvin and Hobbes say? Verbing. Weird language. I guess this is, you know, whatever. I mean, I just, I kind of want to find whoever did that first
[01:03:32] Speaker B: and you know, that's your, that's your hangout. Okay. Yeah, yell it.
[01:03:36] Speaker A: Hey, let's, let's go to the restaurant and get some eat. I'm hungry. I want some eat anyway, so, you know, I don't think that AI or neural nets or anything else really has a magical ability to de rugify landscapes. I think it really is a matter of blood, sweat and tears. I mean, I, I mean there are some cases where like there's a classic problem called max, max flow.
You learned about it in first semester. Data structures and algorithms. How do you, you know you have a network, each edge has a certain capacity.
You want, you have a source, you have a destination. You want to pump as much flow as you can from the source to the destination.
How do you do this?
Well, if you just did this by kind of purely hill climbing greedy local improvement algorithm which always tries to add more flow, turns out the landscape is rugged, you can get stuck.
[01:04:41] Speaker B: See, I thought that part, I thought part of like, I don't know if it's machine learning theory, I'm not sure the right field or whatever to say this.
[01:04:50] Speaker A: Let me tell you the punchline. So you might, you might think, oh, this problem might be NP complete if you just expand the space of possible improvements that you're willing to make a little bit.
So if you're just willing to sometimes add kind of anti flow, it's actually a lot like Feynman's idea of antimatter going backwards in time. If you're just willing to add flow which gets from here to there partly by doing negative flow backwards on some places.
That expanded palette of possible moves, possible improvements, de ruggifies the landscape.
Because now points in the landscape that were not neighbors before, now they are.
And so this changes the structure of the landscape into a nice Mount Fuji. And now with the, this slightly expanded set of moves, it's no problem.
You can find the optimum in polynomial time.
[01:05:52] Speaker B: Well, how is that different than adding another layer of nodes or adding more compute Just kidding. But like adding more nodes. That's what I was going to say is I thought it was shown in like super high dimensional, well, high dimensional spaces which when you add nodes, that's increasing the dimensionality of the network and that almost there's a guarantee past a certain point perhaps that there's always a step in the right direction because it's so high dimensional.
I might be misremembering that, but that sounds like what you were just describing.
[01:06:27] Speaker A: It is absolutely true that some problems which are non convex and rugged in low dimensions can become convex in high dimensions.
That's absolutely true.
It's not true of all of them.
We can, we can go into some examples if you want. But so yes, sometimes it's, it's akin to a, I mean, one way to view it is what people call relaxation. So going back to our Boolean satisfiability problem, there is a mathematical generalization where, of a similar problem called max cut, where rather than having Boolean variables which can be true or false, they're like little switches which can be up or down, or they're like little iron atoms or in quantum mechanics spin one half particles which can be up or down.
Well, let's let them be vectors which can point in any direction in a high dimensional space and let's try to let them work out their conflicts by being able to point in all sorts of different directions in that space.
This does sometimes render previously unsolvable problems solvable. That's true.
There are some issues here though. One is that if you're in a very high dimensional space, so if you're literally in an exponentially high dimensional space, even if your problem is convex, there are now exponentially many directions in which you could try moving.
Right. So we've sort of traded one exponential for another.
So I don't, I don't think this. Again, I don't think it's a silver bullet. But yes, it's an important tool in the toolbox.
You know, I mean, incidentally, yes, we don't know that P and NP are different, although I really hope they are. I think it would be kind of boring if they were the same.
I think a couple of things. I think that first of all we're actually ironically at an early stage of understanding what algorithms can do, even good old fashioned polynomial time algorithms you can run on your laptop.
We have a handful of strategies that we know about.
There's divide and conquer where you break your problem into smaller pieces and solve each piece and then do that until the pieces are so tiny they're trivial. There's dynamic programming, which is kind of the same idea where as you start going down your tree of possible, your branching tree of possible solutions, you find yourself in the same place many times. Well, just remember that you were there before.
And in some cases the number of different places you have to visit is only polynomial. So boom.
There are ideas from optimization, including linear programming and convex optimization.
There are beautiful ideas from duality. There are, there are things like the high dimensional relaxations that you just described.
And yet the funny thing is we don't know if we know, we don't know what we don't know, right? We don't. There might be all sorts of very different algorithmic strategies out there that we haven't thought of yet.
It may be that P, the class of polynomial time algorithms is much larger than we imagined.
Right? That's a possibility, even if it doesn't extend all the way to np.
That's one answer. The other answer I would say is that I don't think a neural network of any kind is going to be able to magically solve a worst case example of an NP complete problem.
But I do think that it like humans, but maybe souped up humans, scaled up humans will be able to, in a lot of real world problems that have structure which is useful to the solver, will be able to rapidly recognize those structures and use them to solve a lot of examples of that problem. Not the worst case examples, but the real examples.
Another one of my favorite examples of this going back to Boolean satisfiability.
One real world use of Boolean satisfiability is telling whether a microchip always works.
And you know, you have a microchip with 64 inputs and 64 outputs. There are two to the 64, which is a lot different inputs you could give it.
You can't just test all of them.
I mean, that's a billion, billion even that would take a while, right?
You can't just test all of them and check.
You want to look at the circuit, the transistors, the and and or gates that are laid out in the chip. And you want a mathematical proof that it will always work. Just like you want to in many cases formally prove that some software will always work.
This is tantamount to proving that a certain Boolean satisfiability problem has no solutions.
That's NP hard. And I'm pretty sure that nothing and nobody, silicon or carbon, can solve that problem quickly in the worst case.
But in the real world case, you hand these Solvers, something with a million variables and millions of constraints that come from a chip with millions of little wires and millions of little gates on it.
And it succeeds. And the reason it succeeds is that this is a designed thing.
Well, it's not designed by an adversary, it's designed by people who want it to work. It's designed out of modules, each of which carries out a relatively simple task, each of which is fairly easy to prove that that little module works. And then you can plug those modules together into a larger proof that the whole thing works.
Now, this strategy precedes LLMs.
You know, back in the world of good old fashioned artificial intelligence, during the neural network winter, there were very clever people building these solvers using ideas like clause learning and so on, where as you start to explore the possibilities, you realize additional facts, additional constraints that were not given to you as part of the original problem. Kind of like proving lemmas help you prove a larger theorem and you recursively add those to the mix. And as you do so, sometimes the problem gets easier and easier.
So again, you're sinking your teeth into structure which is there.
And I think that this is what we do when we look for potentially, when we're looking at a potentially hard or even unsolvable problem.
But we're hoping that this example we can get a handle on, or perhaps a whole cloud of examples, a whole class of examples we can get a handle on.
And so we throw the kitchen sink at it trying to figure out whatever we can about it.
[01:13:52] Speaker B: Is that conversation
[01:13:56] Speaker A: I see you're trying to bring this back for a landing, is it? Well, yeah, yeah, I, it is. Computer. You know, I am happy to design, I am happy to view computation as a broad term that includes, it includes what brains do, it includes what markets do, it includes what cells do. Right. I, I mean, you know, saying no, no, no, if it isn't what theoretical computer scientists mean it isn't, it doesn't count.
That would be like if I overheard a slightly new agey conversation in Santa Fe and I said, don't use the word energy.
Energy has a specific meaning in Newtonian mechanics.
[01:14:41] Speaker B: You're in Santa Fe, you've been exposed too much.
[01:14:44] Speaker A: But, you know, like, he has such a negative energy. It's like there's no such thing as negative rest, mass energy.
[01:14:52] Speaker B: But you run the risk then of deflating so much that you view everything as computation. So there has to be a boundary.
[01:14:58] Speaker A: Exactly. There has to be a boundary. I mean, I think what happened in 1936 to the idea of Computation is very interesting because before then, mathematicians were aware that some problems could be solved by a sort of mechanical process.
And some people called it an effective procedure or some similar compound word in German. And some people called it an algorithm, but it wasn't quite clear what it was in general. It felt like a kind of we know it when we see it thing.
And then Church and Turing and Gode come along and say, no, we have a mathematical definition of what an algorithm is, what a computational procedure is, and you don't have to like it, you don't have to think it covers everything, but it really seems to cover everything. Pretty reasonable, right?
And so this brings us to the Church Turing thesis that it does cover everything reasonable, and the physical Church Turing thesis that it covers everything which could actually be built in the physical world.
And it kind of even covers quantum computers. Quantum computers can do some things faster, we believe, than classical computers can, but we don't believe they can solve undecidable problems. There are some people who talk about solving undecidable problems with black holes and stuff, but I think everyone kind of agrees that that's getting.
Well, that's another layer of exoticism and
[01:16:34] Speaker B: energy. Exoticism, man.
[01:16:36] Speaker A: Exactly.
If you have black holes and time machines, yes, you can solve undecidable problems. But you know, people like me probably take that as a proof that we can't have time machines, which is sad. I would like to have time machines. But anyway. But we don't really know. Okay, we don't really know.
But I can certainly say it is hard to come up with a mathematical procedure that isn't at some level computable, because it's hard to come up with a physical system that at some level a good old fashioned Turing machine or a laptop, which could be always compiled down to a Turing machine if you really had to.
If it can simulate your system, then what your system is doing is computable.
But let's be clear about what a vacuous statement this is, right? This is literally saying, oh, because your brain is made of elementary particles. If I had a computer the size of the galaxy and I could do elementary particle physics really well, and I could do molecular dynamics really well. I could simulate your brain. So ha.
Well, kind of who cares, right? I mean, you know, Philip Anderson wrote one of the founding articles of Complex Systems, which is more is different.
You know, it's true that biology somehow rests on top of particle physics, but in a way, does that help us do biology?
Right?
I. It's true that our brains rest on top of biology, does that help us understand our brains? Well, maybe part of the time. Some of the time.
I'm actually very.
I'm very skeptical that that helps us understand art.
I mean, maybe we do art with parts of our brains that were. You know, it's a case of acceptation. Maybe it's parts of our brains that were designed to do things that we had to do on the savannah to survive and run away from lions. Okay, but does it help us understand art now? I'm not sure. I doubt it.
I actually really hate this evolutionary psychology thing about, well, you know, the reason I'll help a stranger in the street is that we used to live in small villages. Like, maybe that's why. But I don't care. I want to help the stranger in the street. Right. I mean, I.
Anyway, so I am willing. So. I love computational complexity theory as a branch of mathematics. I want people to know about it the same way English teachers want you to know about Shakespeare.
I think it has some lessons for us.
Those lessons range from, it can actually solve a concrete problem that you want to solve to. It's a metaphor, a lens that may inspire a way of thinking about the brain or the cell or society, you know, But I would never say that it is the end all and be all of what makes the notion of a problem, the notion of what makes problems easy or hard, or certainly the notion of complexity. But it is something that people should have in mind. The same way that they should know about the lens of evolution, they should know about the lens of economics and game theory. They should know about the lens of deep readings of narratives.
We should all.
Yeah, it is one of the many ways that we should look at the world.
[01:20:25] Speaker B: But so, like, I mean, thinking about how we explain. So science is about understanding and explanation.
Yeah.
[01:20:34] Speaker A: Well, I'm so glad to hear you say that. Some people think it's just about prediction and they have rocks in their heads.
[01:20:39] Speaker B: Oh, well, it's supposed to be about explanation and understanding.
[01:20:42] Speaker A: Right.
[01:20:42] Speaker B: But prediction is part of that. Right, but. But I kind of. I don't know if this is an interesting thing or what, but, you know, since the Turing days and since neurons were modeled as logic gates, and especially since AI has come along, everyone wants to point to computation as an explanation for what's going on when they're talking about their favorite cognitive function. But alongside this, in the past 15 years or so, dynamical systems theory has been used more and more in terms of looking at lots of different neurons in high dimension. And then you Use some sort of dimensionality reduction technique, and you look at their flow fields in these lower dimensional state spaces, et cetera. But the interesting thing is that someone will be giving a talk and they'll show their little trajectory in state space, and it's a trajectory. And then they'll say, and so that's computing. That's where it's computing. And there's no computation there. It's a flow field. And so my question is like, what is wrong with the flow field as the explanation? Why do you have to magically throw in the computation? It's like an assumption that I don't know if there's merit for that. Is there merit for adding computation magically to the flow field?
[01:21:57] Speaker A: Well, I think sometimes there is.
In fact, my PhD thesis was about analog systems. Dynamical systems. Yeah. Okay.
[01:22:05] Speaker B: I don't know when your PhD was, but I found this 1991 paper on predictability and undecidability and dynamical systems. So I know you think about the relation between dynamics and computation, so.
[01:22:15] Speaker A: Right. And for a while, especially in the 90s, I was fascinated with analog computation, computation with things that are not bits. And there's a really interesting history of this. Right. I mean, Claude Shannon, the hero of communication theory and information theory, built things he called the general purpose analog computer. And analog computers made out of pulleys and tanks of water were used on both sides of the Iron Curtain, like into the 1970s to simulate economic models and so on. And I think there's some wonderful parallel world in which the transistor was not invented and we're teaching generations of students to build things out of, you know, pipes and valves and, you know, little governors spinning around.
And that's almost, but not quite, a Bruce Sterling and William Gibson novel. They based theirs on Babbage's Difference engine.
So, you know, but you think computation
[01:23:24] Speaker B: should be in there, that when you point to a trajectory, you can say that, oh, that's computation. That's what that is.
[01:23:30] Speaker A: Well, so, for instance, you know, linear programming, which is the stupidest name for a problem ever, goes back to, you know, operations research. And anyway, what is linear programming? You have a bunch of variables. Each of them can take any real valued value.
And you have a bunch of constraints and you have some function of them, like the sum of all of them that you want to maximize within those constraints. How do you do that?
Well, we think of this as a computational problem, but fundamentally all of these things are real valued.
The coefficients, the constraints are real valued.
What economists would call the prices and the budgets are real valued.
And in fact, there is a beautiful analog algorithm called the Newton flow, which, you know, says, well, basically put a repulsive force each. Let's see. I like to describe this problem as you have a cathedral. The cathedral has a roof made of these different planes. Each plane is a constraint. You have a balloon. You release the balloon. It tries to find the highest point on the cathedral roof.
It finds a point where it's at kind of a peak, where these facets of the roof corresponding to constraints hold it in place and keep it from going any higher. That's the linear programming problem. People usually describe it in terms of chocolate cookies and running a bakery. And it's really boring. Anyway, so it's a cathedral, damn it. It's a high dimensional cathedral.
So there's this analog version where sort of put a little electric charge on the balloon and put some of that charge on each of those facets in the roof to repel the balloon.
But, you know, now, but the balloon also has some buoyancy, so it will rise to some level.
It won't quite be touching the roof because it will be pushed away by the, by the electro, the electrostatic repulsion between it and the roof, which is of the same charge. Now increase the buoyancy or equivalently decrease the charges, the electric charges, to make the buoyancy stronger and stronger compared with the repulsion.
And as you do this, it follows a continuous flow which is guaranteed to reach the optimum at the limit where the buoyancy is overwhelming the repulsion.
[01:26:12] Speaker B: That's like a cybernetic approach almost.
[01:26:14] Speaker A: But.
[01:26:14] Speaker B: Yeah, go ahead.
[01:26:15] Speaker A: It is very. Yes, exactly. And I, you know, a few years ago I reread Norbert Wiener's Cybernetics. It's still pretty readable.
And so, you know, I would say that this is an analog system which in this case we designed to solve an optimization problem which can also be solved by digital means, can also be solved by the simplex algorithm and all these. Or the ellipsoid algorithm, all of these are digital algorithms.
In fact, there's a deep analogy between the ellipsoid algorithm and the Newton flow that not many people know about.
So I think, especially in high dimensional spaces, it is often reasonable to say that this continuous flow is solving a computational problem.
It is optimizing something.
It is, you know, it's doing something that if you did it with more digital means, you would certainly call it computation. So at least from the point of view of, of what it achieves, you would call a computation.
You Know, but going, but going back to the, going back to the brain.
I think the wonderful thing about humans is we don't have an objective function.
We have objective functions that we choose for ourselves, that we work to optimize for a while and that then we abandon and try optimizing something else instead. Right. And that's a wonderful thing.
That's a wonderful thing.
That freedom to choose what you're trying to optimize is the same as the composer choosing what kind of piece to write, the mathematician choosing what to try to prove or disprove.
That's where human freedom and flourishing lies, my friend.
[01:28:02] Speaker B: But see, that's. You're talking about the whole human, which I'm very, very comfortable with in terms of like a human computes, a human optimizes or an organism. But the dominant paradigm today is what algorithm is the hippocampus running?
What algorithm is the hippocampus running to accomplish the computation that it has to solve in this very particular situation.
You know, and so there's a billion computations and algorithms that people are just plastering on to different parts and processes in the brain. I just.
And there's merit to that. And it gets you a long way. I just don't know that it's the end all as the.
It is the only game in town these days in. Or the dominant game in town. So that's.
[01:28:47] Speaker A: But isn't it reasonable, isn't it reasonable to say that, yeah, there are parts of the brain that are, that are solving a fairly well defined task? I mean, they're like v1 different.
[01:28:57] Speaker B: Well, solving a task is different than computing the solution to the task, perhaps, or maybe, I don't know if these are just word games. That's what I don't want to do is end up playing word games about it.
But, you know, but the larger picture. Go ahead, go ahead.
[01:29:09] Speaker A: I mean, a long time ago, like I read this book by Penti Canerva called sparse associative memory, which was, you know, a pre neural network, but still in some ways network inspired, kind of connectionist inspired, if I recall.
I don't remember it very well, but it was a pretty creative idea of like mathematically, how do you define and build an associative memory?
Because clearly that's what we've got, right? I mean, I don't have a random access memory. If you ask me to jump to a certain point in a speech or a poem I've memorized, I can't do it. I will start at the beginning, or at least the beginning of a section that I remember as a landmark. I will work my way forward. And, you know, I have a forward associational memory. If you ask me what line came before a certain line that is really hard for me to do if you repeat it. If you give me a string of words and ask me to repeat them, I can do that in the same order as I will make some mistakes if it's long, very hard for me to do in the reverse order. Which is why I always wondered, why did Noam Chomsky ever think that we have stacks in our brains that push and pop? If we had stacks in our brains, I could take the words you gave me and pop them back off and it would be last in, first out, and it would be really easy for me to do it in the reversed order, but it's much harder to do.
I can recite the Alphabet backwards because of an awesome they Might Be Giants song.
[01:30:40] Speaker B: Oh, nice.
[01:30:41] Speaker A: Yeah, only because of that song. Otherwise, like, so I can pass the drunk test, I guess.
[01:30:46] Speaker B: Yeah, yeah.
[01:30:48] Speaker A: So, I mean, I think these things are some kind of hint as to what sort of memory retrieval we have.
And,
[01:31:01] Speaker B: but see, that's fine to say it's some sort of hint.
That doesn't mean it's a computation. Right. You know, yeah, I'm just being difficult myself. But, but yeah, no, I think that it's very useful hints, very useful metaphors for understanding things.
That doesn't mean that the model is the thing that you're modeling.
[01:31:24] Speaker A: That is certainly true. And it doesn't mean.
Right. In theoretical. In most of computer science, we build general purpose tools like programming languages, but then we use them as platforms for algorithms which do one well defined thing.
Right?
So now we have these peculiar new artifacts which seem to be able to do many things.
So they're kind of. I mean, I, I have computer scientist colleagues who get really mad if you say that the LLM is carrying out an algorithm. They'll say, no, it's not algorithmic. It's like, well, come on. At the end of the day, it is. It's like, no, it's not, because it's, it's doing this, you know, real valued, deep, hard to interpret thing which is not carrying out well defined, a well defined sequence of steps. It's like, well, but it kind of is on the micro level because we are running it on a computer. It's like, well, no, but that's not really what matters anyway.
So even within the world of silicon intelligence, I think people argue about this a lot.
[01:32:31] Speaker B: Okay. All right, Chris, last question here. And this is actually from someone who was part of the discussion in the complexity group that you've joined and whether you have an answer to it or not. I just thought it was a great question and I'd love to see which exactly. Algorithms your brain is going to compute to answer this question.
[01:32:53] Speaker A: Okay.
[01:32:55] Speaker B: Doesn't that sound silly just saying it that way anyway,
[01:32:59] Speaker A: Right.
[01:33:00] Speaker B: Crank it up. So the question is like if you were going to. All of a sudden, if you're going to be forced to. I'm adding this little coloration to it. But if you were forced to abandon computer science. Not abandon computer science, but to study the brain. Right. The King of England in the 1600s decreed, in the 1400s decreed. You, you must not write a fugue, you must study the brain. How would you, what, what would be your interest and like, how would you do it from. Maybe from a, from a computational complexity or just computer science.
What would you be interested in doing and how would you go about doing it?
[01:33:37] Speaker A: I would reserve the right not to do it that way.
[01:33:40] Speaker B: Off with his head.
[01:33:41] Speaker A: Sorry.
[01:33:42] Speaker B: Not to do it. Not to do the computer science thing.
[01:33:45] Speaker A: How I had to study the brain.
[01:33:46] Speaker B: No, he didn't. He didn't. But it better be beautiful.
The fugue better be beautiful.
[01:33:50] Speaker A: Better be beautiful. Okay, and, and with not too many notes.
Sorry, that was an Amadeus quote.
You know, I really believe in this thing I said before about lenses.
And I believe that when an intellectually honest person approaches a question that they should start out by being very agnostic about what kind of reasoning will be useful to help solve that question. And for that matter, you didn't ask us a question. You said the brain. So also agnostic about what kind of question to ask.
And the, the fact is, to be honest, I am in, in my day job, I mean I, I work on policy and law a little bit, but in my day job I mostly work on well defined mathematical things.
There are things I chose, but they still spend, they're still pretty well defined.
With the brain, I would have to start at a much more kind of empty handed. I would really have to come to it without very many preconceptions.
Like I said, different fields have very different ideas about what constitutes a good question and what constitutes a good answer to a question.
Even the word model. What's a model? Different fields of wildly different definitions of what a model is. And some people say, no, this is a mechanistic model. Someone else will say, no, it's not mechanistic at all. Where's the mechanism.
So I will tell you that what I do, my M.O. when I enter a new field is I find someone who will tolerate a lot of stupid questions.
So hopefully the King will order 50 or so people to do that.
And I ask a lot of stupid questions. And if I'm really lucky, then on the 10th or 20th or 50th question, they're like, huh, that's a good question.
And then we're off to the races.
And if I, if that doesn't happen, well, then I'm not going to have much to contribute. And honestly, there have been times in my life where it's gone both ways.
[01:36:14] Speaker B: I would hope so if it hadn't. You're not trying hard enough, right?
[01:36:18] Speaker A: I mean.
[01:36:18] Speaker B: Yeah, you gotta put the effort in.
[01:36:22] Speaker A: Yeah. So I think that is not a very satisfying answer.
You know, if you pressed me harder, I would say I would retreat to something like the little cortical column that everybody says has this repeated structure with, what is it, six layers of these very specific neuronal types. And they must be there. It must be that way for a reason.
And then I would try to go hang out with the people who are struggling to understand that. Or I would hang out with my friend Stuart Firestein at Columbia, who studies olfaction, which is like a fascinating sensory thing, which is clearly more complicated than vision. Not that vision is simple, but, you know, how are odors encoded in the brain? What kind of sparse coding where there's something that looks like it's almost a math problem.
[01:37:20] Speaker B: Okay, right. So specified enough like it's close enough to a veritable problem in the mathematical sense that you could approach. So you could still approach it from that complexity, kind of computational complexity lens, by the way, I use the word brain, but the actual question was cognition in general. So I substitute a brain for cognition. So you don't have to restrict yourself to brain here, but you'd want something that's.
At least there have been a few wisdom teeth sunk into at some point that it seems almost well formulated or something.
[01:37:56] Speaker A: Yeah, I think what I would do is I would come to those 50 people that the King has ordered, much against their will, to tolerate my presence.
And I would say, look, here's what I know. I'm willing to learn other things, including totally new things, but I'll be starting from scratch. I would love to learn new things, but you really will be just teaching me. And there's no guarantee I'll help with anything about anything.
But here's what I know and what, what either subsystems in the brain anatomically, or.
What tasks do we do that you think are amenable to this study?
I mean, I will say that there is a lot of work that I don't like. If you say, oh, well, let's hire a bunch of people on Mechanical Turk or prolific to do this little game, I'll say, forget it. Chop off my head now. I mean, I. I don't like that kind of work very much. I think it's very artificial.
I think it's scaling in a weird. In a way, I think it's like. That's very much like we're looking under the lamppost because somebody gave us this way to do shallow experiments on lots of people who don't really care about the experiment.
I'm not into that.
You know, I'm not very much into.
We'll have a bunch of freshmen and we'll give them each five bucks and have them play game theory things with each other or memory games. And I'm not really into that. I mean, I know this is how a lot of the field works.
To be honest, a lot of those studies leave me awfully cold.
I hope I'm not offending you or your friends, but, I mean, I think that when.
I do think that when there's a strange thing that happens in an optical illusion, for instance, you don't need to try it on 10,000 people for a penny each.
You know, you're seeing something that says something about how at some level, information about a visual scene is encoded.
I think that's really interesting. I mean, I.
Maybe I did just. Did I defend you? Do you do that kind of work?
[01:40:09] Speaker B: Paul, first of all, I'm really hard to offend, but, no, I. I don't. I'm not in psychology. I'm in science. I do careful, careful experiments and data.
[01:40:18] Speaker A: What do you think about FMRI stuff?
[01:40:21] Speaker B: And that's the end, folks. I'm not going to answer that.
[01:40:26] Speaker A: Good. Yeah, yeah,
[01:40:29] Speaker B: I. I know some very fine people on both sides.
[01:40:32] Speaker A: That's very. Well, well said. Well said.
[01:40:37] Speaker B: All right. So, you know, we did not talk about your algorithmic justice work.
That I know that you do your decarbonization work, but so, so, but we, man, we. We covered a lot here. So I appreciate you coming back on to do this with me again, and I hope that the listeners got a sense, too, of just the way that you think about things and the way that you carefully move through in your own head.
It's well worth looking into the book the Nature of Computation it's just. It's got everything. It's got everything in there. It's so thorough. So there's. I think there's something for everyone. So, anyway, so thank you, Chris, for spending the time again. Appreciate it.
[01:41:20] Speaker A: All right. Thanks, Paul.
[01:41:28] Speaker B: Brain Inspired is powered by the Transmitter, an online publication that aims to deliver useful information, insights and tools to build bridges across neuroscience and advance research. Visit thetransmitter.org to explore the latest neuroscience news and perspectives written by journalists and scientists. If you value Brain Inspired, support it through Patreon to access full length episodes, join our Discord community and even influence who I invite to the podcast. Go to Brain Inspired co to learn more. The music you hear is a little slow jazzy blues performed by my friend Kyle Donathan. Thank you for your support. See you next time.
