MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams

34:46And I appreciate them for supporting my work and sponsoring this podcast. One topic I thought might be fun to go over is you wrote this paper about the likelihoods of these various conjectures in complexity theory. And I pulled a few of these that were kind of minority opinions or maybe, you know, less common takes. So here's to hear your rationale. Okay. Okay. One of them, the well-known one, P not equal to MP or P versus MP, you assigned an 80 % confidence that they're not the same. Yes. And I think most people say much higher confidence. So why would you assign such a low confidence that they're not the same?

35:32It's interesting because I think I originally had something like 75%, percent. But then my college classmate, Scott Aronson, was like, how dare you? He sort of called me out and like, okay, fine. For you, 80 percent. Fine. I guess my point is that we really don't understand polynomial time computation as deeply as we think we do. And there are surprises like all the time in the power of algorithms. There are very few surprises in terms of lower bounds. Like when we are able to prove a lower bound, typically it's something we very much expected to be true, but it was hard to prove. It was hard to prove.

36:25Somehow we pulled it off. We got what we expect to be true. But all the time in algorithms, people are finding algorithms where it's just like surprising. Just wait, what? How do you get something that fast? So this just happens over and over. When I was younger, when I was first thinking about P versus MP, I had an intuition for what should be. And what I've understood over the years is that my intuition for what should be is often just wrong. And I'm having to revise my intuitions all the time. So when something like this happens often enough, you start asking yourself, what do I really understand?

37:23Do I really understand, Beers and Beers? Like, I mean, I understand the statement, right? Like, it's just one of those problems where somehow it is not so difficult to make formal, to write down mathematically, but to actually know what the answer is, is just orders of magnitude more difficult than it is to phrase the problem. And complexity theory in particular is littered with statements like this, where the space of algorithms is just that vast. So if you just keep getting surprised over time, you're just like, well, what do I understand? Maybe it was just misplaced confidence. Okay, what about this one?

38:11So exp not equal to nxp, or would you say nexp? Oh, nxp, yeah, x versus nx. So this is like the exponential time of p versus np. for x not equal to nx or nexp you gave it a 45 chance and if this is the p not equal to np equivalent but for exponential time why is your yeah why is it so low oh because exponential time albums are even more powerful did i really say 45 i mean you did for nx versus x or nx versus co-nx. Yeah, nx not equal to x 45%. It's in this table. So in other words, I believe nx equals x more than I believe they're different, right? So yeah, let me try to explain why. So you can think of the NX versus X question as some special case of P versus NP, where instead of looking at the arbitrary SAT problem, I'm looking at a SAT problem, which is extremely compressible.

39:26So there's like a really small little computer that is exponentially smaller than the length of the instance, and it just outputs the character on the line number and the column number for the DIMAX CNF, like the CNF file, okay? So it's like an extreme compression of some file. So it's like you zipped it down to something exponentially smaller than its original length, okay? So it's like some super compressed, extremely highly regular SAT instance. So I give you that, and I ask you, when you unpack this thing, decompress it, is the result going to be satisfiable or not? And I want you to solve this in time polynomial in the decompressed representation.

40:20Okay. So the point is that this is SAT, but in some very special case where the thing is extremely structured. So the idea, one conjecture for why SAT solvers work in practice, like one, I mean, this is, I mean, conjecture may be overkill because, I mean, this is just, this is not even a well-formed mathematical statement. So one hypothesis for why sat solvers work in practice is because the real world is highly structured. The real world is governed by physical laws that are not random. They're not arbitrary. Like from a very small number of rules, we can recreate so much of science. So what arises in practice from designs of hardware and things like this are often extremely compressible.

41:19They have to be extremely compressible. And so maybe it's true that, you know, every science which has a highly compact representation can just be solved efficiently. This is the idea of whether, you know, in X equals X. That when it's really, really structured like that and super compressible, there is some advantage. It's not like a completely random. and since it's not like something arbitrary it's no it's in fact very very special the other one is 80 likelihood on nx equal to co-nx and you wrote why would a self-respecting complexity theory do that and so yeah i was curious why that's such a contentious statement so nx versus co-nx let's let's first talk about MP versus co-MP.

42:13So co-MP is like the class of sort of complements of MP complete problems, like unsat, like checking whether something's unsat. Now, from the time complexity point of view, there's no difference between checking sat and unsat. You can always flip the answer. But from the complexity point of view, if I ask you, does co-MP equal MP, what I'm asking you is, could you prove to me that a formula is unsatisfiable with a short proof? When it's satisfiable, I can give you a short proof. I can just give you the satisfying assignment. You plug it in, check that it works. But if it's unsatisfiable, if no assignment works, we're saying for all assignments, the formula is not true.

43:03Can you flip that to an existential statement say, oh, there exists this little proof that makes it work. So people don't believe that MP is equal to co-MP. And in fact, like MP different from co-MP implies P different from MP. But so this is the exponential time version of MP versus co-MP. So it's co-NX versus is NX. The reason why I think these are likely to be equal is that if a little birdie sat on an NX machine's shoulder and gave it a little bit of advice about what the co-NX thing is doing, then the NX algorithm can actually solve co-NX problems. And so let me explain, let me explain what's the little birdie what the heck is the little birdie saying so because nx problems can run in two to the n time and two to the n squared time and things like that running an exhaustive search over all possible inputs of linkedin is no problem for nx so what a little birdie can do is say, okay, suppose I want to verify that this particular instance, let's say we can talk about an unsat, but some compressible unsat problem or something.

44:38Suppose I want to prove that this compressible unsat instance is a yes. How am I going to do that with nx. The little birdie will tell me the total number of inputs of length n, which are a yes. Okay. So it will just tell me some string, which says, here's the total number of inputs of length n. You gave me a length n input. Here's a total number of inputs of length n that are a yes. Okay. Okay, so this advice, this little, you know, Bertie's advice doesn't take very much, like to encode a count. It's like order in bits to encode a count of things. So what does the NX thing do to prove a co-NX thing?

45:32What it does is it guesses the things which are a no. So I'm trying to prove unsat. So unsat means yes, sat means no. So the NX thing guesses those things which are no. The no things it can answer, right? If it's a sat thing, it can just guess the answer to each of the no's, okay? So it guesses the answer to each of the no's. It verifies all those answers, and then it checks the number of things it guess is what the birdie told it. Once it's done that, all the no's have been covered. So everything else must be a yes. So it can actually prove a yes by just exhaustively finding all the no's and ruling out any other no's.

46:21But the big question in my mind is where do you get the little birdie? Where do you get the little birdie advice from? Yeah, yeah. So I've studied what the little birdie gives you. and it seems to me that it is possible that this little birdie itself can be constructed in NX and if so then we'd just be done like in NX you figure out what the little birdie would tell you and then use that to just flip the answer sort of guess let's sort of guess all the things which are no so what remains must be a yes and we talked a lot about time complexity And you mentioned a little bit, this advice, I guess, is kind of space complexity.

47:04And I know you had a major result relating space and time complexity, basically simulating time complexity with space complexity, but lower than it's been done prior. Could you explain what it was before your breakthrough results and then maybe the intuition behind your breakthrough result? In general, the problem is the following. I give you an algorithm that runs in time t, and I want to know, is there another algorithm that uses space much less than t? Uses the amount of memory, like units of memory much less than t, and still solves the problem completely. Still completely simulates the thing perfectly.

47:52um one intuition for why you might think um this question just can't be solved or some problems there's just no way to improve on the space is if you think of like the pro like a lot of problems in dynamic programming like let's say i have um some logic circuit that i want to evaluate and all the gates are provided to me in a row and all the wires sort of flow from left to right. And then, you know, I start with information on the left. I want to compute the information on the far right. And all the, you know, all the bits are flowing left to right by wires. The natural way to evaluate such a circuit is you start with, say, the inputs on the left for each gate in turn in the line, you look at its inputs, its inputs have been determined, there's some bits, use that to compute the value of that gate, you pass the values of that, you know, the output of that gate forward, okay?

48:58But if that circuit, you know, has T gates in it, you know, it will take about T time to solve, but it will definitely also take about T space in general, right? Like, The circuit could be wired up in some wild way, and there just might not be a way to save space for an arbitrary circuit. But already in 1975, people were studying this kind of question and finding counterintuitive answers to it. So Hopcroft, Paul, and Valiant, based on work of Patterson and Valiant, showed that time-t algorithms, at least in this so-called multi-tape Turing machine model, very powerful model, can be simulated in space t divided by a log of t.

49:53So, I mean, it's like you get some space savings, but it's only like a log t factor. And the way this is done is quite counterintuitive. I mean, even though there's only a log factor there, it was pretty shocking. That development was extended to random access models of computation later and more general models of computation. So like in the late 70s and early 80s. So it was known for pretty much any reasonable model of computation that time T can be simulated in space about T over log T. But there was a hidden, maybe not so hidden, gotcha in the space efficient simulation. It needs an exponential amount of time to run.

50:53So like you, there's a time space trade off. Okay, if you really want to save some space, you got to blow up the time by a lot. Nevertheless, yeah, it was kind of commonly conjectured that this T over log T space was about the best you could do. And that you were probably not going to get T to the 0.9 space or something much more efficient. Um, so yeah, it was a big surprise to me, uh, like that you can actually put time T and space about square root of T. Again, there's an exponential running time just to, you know, give the full caveat out there. But, um, but it's still very surprising. Like this holds for any kind of time t algorithm like including something that might be outputting you know something pseudorandom some you know something from cryptography you know like it's not at all obvious that every such process could be compressed to only be need like square root of t space and still get the job done still compute whatever function was being computed i mean i I know it's probably super involved, but if you could just, a high level, what's the trick?

52:18How'd you do it? Well, the trick for me was to read James Cook and Ian Mertz's paper on tree evaluation very, very carefully. I mean, and just knowing the landscape around P versus P space and knowing what Hopcroft, Paul, and Valiant did. And yeah, so I can give you a very high level idea of kind of what's going on and how what they did is useful. so Hopcroft, Paul, and Valiant the way they were modeling space bounding computation was in a particular way that seemed pretty general at the time but turned out to be restrictive in ways that we just didn't anticipate so the way they thought of it was I'm going to take like certain I'm going to break the computation up into little pieces and And I'm going to write pieces of the computation, like little bits into the memory, but I'm only going to do that over blank space.

53:32I mean, this is something that sounds natural, right? So I'm going to erase pieces of memory, and then I'm going to overwrite that blank space with a piece of memory. So I'm being very destructive in a certain sense. But this is a natural thing you do, right? If you want to swap something with something else, you often just erase. But there are ways to swap without erasing. So there's a common little trick that is taught in CS courses. So if you require everything to be written into a blank register, then if you want to swap the contents of two variables like x and y then you've you've got to have a temporary register like you move one into the temp you erase it you move y into the into there and so on right but if you don't want a temp you can achieve the same thing uh with just x oring the the registers bitwise or if you've got numbers you can add and subtract Okay.

54:42In three instructions, clever instructions, adding, subtracting, or XORing, you can actually swap the contents of two registers without needing a third. Okay. This is kind of the starting point for thinking about like, well, why does it matter if you're always writing into erased memory? So what James Cook and Ian Mertz showed at a very high level was they were studying a certain problem called tree evaluation, whatever that is. And the problem had an algorithm where you had a little stack and you're always sort of like popping and pushing on the stack. But you are always writing computation contents into erase memory.

55:42What they realized was that if you allow computations to XOR bits of memory into existing memory, then you can save a lot of space. So if you're really, really careful about how you XOR things, you can basically recover what's in your memory without storing all of it at once. you sort of offload things to computation and you xor on top of things very very cleverly you can get like nice cancellations of things you don't want and and keep around things you do want yeah so i mean that is a high level uh idea of how this stuff works and then going to square root is it just an extension of that or is it a completely different so the the way it works with square root is square root just happens to be kind of like the optimal trade-off in this tree evaluation business.

56:38So what you do is you break the computation into square root of t time intervals, and each time interval has about square root of t steps in it. And what you do is you give a particular way of simulating this thing so that you're only kind of holding about a constant number of blocks or like of these time intervals in memory at any point in time. Like you're only holding a small number of these time intervals, like records of time intervals in memory any point in time, which is entirely not obvious how you would do it. but it's some sort of sweet spot to set the square root of t. It's like the minimum setting of trade-off.

57:31Say I want to break the computation in the intervals and the intervals have a certain number of steps. If I set it to be square root of t, then the number of intervals and the number of steps in each interval is about the same. So, I mean, that was a long-held result. I mean, you mentioned it was 1975. that's maybe almost 50 years where if you come up with something like that and you you I guess you're writing it out you're thinking through and then you see it what is that moment like so I you know I'm I've been around long enough to have been deceived by myself many many many many times so yeah I guess the the first two or three times I thought about this um I just thought this is another one of those ideas that can't possibly work.

58:21There's no way. There's just no way this works. Um, so I would just kind of leave it and then come back to it sometimes when I was bored of whatever else I was working on. Um, like I, I, it was a pretty slow process of convincing myself that this could possibly be true. Like I, I thought there was either a bug in what James and Ian was doing somewhere, or there was a bug in my interpretation of what's happening. I thought there had to be a mistake for a long time. And the only way I got over that was just writing it down over and over and over in different ways, sort of writing and rewriting and writing and rewriting and adding more detail, and then maybe finding a different way of explaining it and erasing and, you know, writing something shorter and just sort of re-explaining it to myself over and over and over.

59:26And even then, like when I submitted it to the um stock conference where it was where it appeared um I wasn't entirely confident that it was correct I was just exhausted from like thinking about it for so long and just thought maybe someone else will find the mistake for me like I'm like I got like at this point like I was just like desperate like I had actually sent it to two colleagues that I trust you know privately and asked them can you help me find the mistake or whatever can you help me understand this and one of them just said like they're basically they just didn't read past the abstract they're like i'm not i'm sorry i'm not going to i'm like they just didn't believe it period just like me i mean they didn't believe follow it, but there was a footnote that you put like in the bottom of some page.

1:00:34After that, after that footnote, then I began to believe it. So then what I did was I just took that footnote and elaborated it in like a later revision, sort of made it what I called the warmup, because I was like, yeah, I've got to do, I've got to write this thing in a way that is airtight so that other people will actually believe this because, yeah, it took me a long time to get used to it, to believe it. Yeah. Wow. What motivates you to solve these hard problems? I mean, what keeps you driven? Because you kind of, it sounds like you got to just bash your head against the wall and maybe you get there, maybe you don't.

1:01:20I try not to bash my head against the wall. And if I'm going to do it, it's going to be a comfortable wall. It's going to be one that's high-end and luxurious or something. I'm going to enjoy the process is what I mean. If I don't enjoy the process of really grinding and trying to understand something, I'm just I'm not gonna do it like uh so I think that if you know if anything is uh one thing that I that I like I I like to involve myself in working on problems where the the grind is actually joyous and and fun yeah um for the other things uh they're just they're mainly opportunistic They're mainly me just taking something new that I see and just fully integrating it with everything I know and following everything to the logical conclusion and just seeing what happens.

1:02:26Like trying not to get emotional, trying not to whatever, just trying to follow everything one step after another. Yeah. How do you pick good research direction? The best kind of research direction, which is very hard to come across, is a direction where you've set yourself up in a way that you can't lose. That like, I have a hypothesis, H, and one of two things is going to happen. Like either I prove H is true or I refute H, prove not H. What I would like to have is a situation where if H is true, then good things happen. If not H is true, good things still happen. Other good things. Like I like to look at things where, yeah, it's a win-win.

1:03:23Kind of if you can find opportunities like this, this is important. Like, I think often I'm not looking at a specific problem. I'm looking at a method. I'm looking at the technique. I'm looking at not the specific proof, but like the space of ideas. And I'm trying to understand what else can be done in the space of ideas. So often I solve problems just by just taking some idea and putting it somewhere else. Do you have a concrete example of where you've pursued something knowing that if you succeed, good. If you succeed in another action, also good. I have some particular research program for which, if it materializes, would actually show that something called the orthogonal vectors problem can be solved in nearly linear time.

1:04:23okay now this um now if that's true then the sat problem can be solved in about the same time as subset sum it could be solved in like square root of 2 the n so this would like truly break a strong eth in like a radical way okay and um i did a lot of work uh in the past showing how Now, if you can improve on the running time of SAT, then you can somehow use that to prove circuit complexity lower bounds. You can take an algorithm for analyzing circuits that's non-trivial and interesting and turn that into a limitation on what those circuits can compute. Okay, so this hypothesis, maybe I won't exactly say what it is.

1:05:21It's a pretty technical statement. But the point is that if the hypothesis is true, then I get this fantastic algorithm for this orthogonal vectors problem. I get this algorithm for SAT. I get circuit complexity, lower bounds from that. I get to somehow prove limitations on what circuits can do. If the hypothesis is false, I can use that hypothesis to actually show another circuit complexity lower bound of a different flavor. So regardless of whether or not the hypothesis is true or false, I'm going to make progress in complexity theory. I'm going to prove a new limitation one way or the other.

1:06:03right so it so sometimes like i mean this can be difficult to do but um usually what has happened instead of something so clean is that i have i i read about some idea or whatever i try to apply the idea i read about some magical algorithm i try to apply the magical algorithm to solve something like SAT, it doesn't work. But I look at my approach. I stay really hard at it. I try to pivot. I try to just extract what I can. And then I get some other type of algorithm. I mean, this is essentially how I approved the circuit complexity lower bounds that first got me a job at Stanford, was I was trying to solve SAT faster with some algorithm.

1:06:54it didn't work but then i realized that that algorithm worked for a large class of circuits including ones we didn't know lower bounds for so then i use that to prove a lower a lower balance yeah so i mean um this is just a general principle that that i've had what what would be your book recommendation if someone wants to learn more on complexity theory yeah so it sort of depends on how deep you want to go. There's Avi's book. Yeah, Avi's book is really nice. If you're looking for something a little more gentle of an introduction, I would say you could read the early chapters of Lance Fortnell's The Golden Ticket, trying to imagine what a world would be like if P equaled MP.

1:07:45I like that imagination exercise that Lance did. On a more technical level, if you're looking for something slightly more technical, you could look at the nature of computation by Mertens and Moore, I think. So this is still not very technical, but Um, but a lot, but it is a textbook, right? Yeah. Um, and then of course, uh, Sipser's, uh, introduction to the theory of computation is like, um, a fairly concise and very well-written, uh, textbook. Yeah. Last question for you is if you could go back to the beginning of your career, knowing what you know now, what advice would you give yourself? So I guess one thing that I did by accident, I guess, which I think people should keep in mind, is that you don't need permission to work on very tough problems.

1:08:55Like, in fact, the tougher the problem, like in complexity theory, there are all these problems where like really nobody has a very good clue of what to do beyond like a few simple structural results. Like, so that kind of levels the playing field a bit. And yeah, like you just, you don't need permission to think about these problems. You don't need like, you know, anybody's say so or whatever. I mean, that's one thing that I would like younger people to keep in mind. I mean, this knowledge is open to the world and it's open to you and you can just go learn it and think about it. And you don't need anybody's permission, especially not mine.

1:09:42Um, yeah, like, um, another thing I think is, uh, to avoid inertia in the sense that like, you know, if you, if you don't think about and reflect, like, where am I going and what am I doing? Um, you can, you know, you can just end up coasting in a certain direction. And I think it's important for people to sit down and truly reflect and think from time to time, like, okay, if I keep going in this direction, is this going to lead to a place that I want to be? And this sort of advice is good for all aspects of life, really. Like, like if I keep, if I keep, you know, just allowing things to be the way they are, am I going to be okay with that?

1:10:41Or do I need to do something? Do I need to, so it's like a little interrupts, you know, in your life reflection and just sort of like, okay, is this, is this where I, do I, do I need to be coasting here? Like, do I need to, yeah, I think, um, like in research for me, I was always reevaluating like, okay, you know, what I do last year and what I do the year before. And, you know, could, you know, like, what do I know now that I didn't know then? And like, you know, am I progressing? I think like, like that sort of self-evaluation, uh, is crucial when you're in grad school, Because, you know, once you're in a PhD program, there are no more like easy metrics to gauge like how good or bad you are doing.

1:11:29And the truth is you're just doing like, you know, like there just isn't such a metric. So all you can really do is evaluate your past self with your present self and compare and contrast to see if you're making progress with whatever it is you want to do. Thank you so much for your time, Professor Williams. I really appreciate it. Yeah, I appreciate you having me here. It's been fun. Thanks.

1:12:19building the ergonomic keyboard that i wish existed here's a glance at the prototype it's a split keyboard so there's two sides this is in the case but yeah we launched on kickstarter and we hit our goal within eight hours of launching i really appreciate it if you were one of the people who grabbed one of the early units we're now working on the long journey of building the tooling now and so if you still want to pick one up i've left the late pledges open on kickstarter so you can grab one there. I'll put a link in the description. Thank you again for watching the podcast and I'll see you in the next episode.