Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111
the following is a conversation with richard carp a professor at berkeley and one of the most important figures in the history of theoretical computer science in 1985 he received the touring award for his research in the theory of algorithms including the development of the admirance carp algorithm for solving the max flow problem on networks hopcroft corp algorithm for finding maximum cardinality matchings in bipartite graphs and his landmark paper and complexity theory called reducibility among combinatorial problems in which he proved 21 problems to be np complete this paper was probably the most important catalyst in the explosion of interest in the study of np completeness and the p versus np problem in general quick summary of the ads two sponsors a sleep mattress and cash app please consider supporting this podcast by going to asleep.com lex and downloading cash app and using code lex podcast click the links buy the stuff it really is the best way to support this podcast if you enjoy this thing subscribe on youtube review it with 5 stars on apple podcast support it on patreon or connect with me on twitter at lex friedman as usual i'll do a few minutes of as now and never any ads in the middle that can break the flow of the conversation this show is sponsored by eight sleep and it's pod pro mattress that you can check out at asleep.com lex to get 200 off it controls temperature with an app it can cool down to as low as 55 degrees and each side of the bed separately research shows the temperature has a big impact on the quality of our sleep anecdotally it's been a game changer for me i love it it's been a couple weeks now i just been really enjoying it both in the fact that i'm getting better sleep and then it's a smart mattress essentially i kind of imagine this being the early days of artificial intelligence being a part of every aspect of our lives and certainly infusing ai in one of the most important aspects of life which is sleep i think has a lot of potential for being beneficial the pod pro is packed with sensors that track heart rate heart rate variability and respiratory rate showing it all in their app the app's health metrics are amazing but the cooling alone is honestly worth the money i don't always sleep but when i do i choose the a-sleep pod pro mattress check it out at 8sleep.com to get two hundred dollars off and remember just visiting the site and considering the purchase helps convince the folks at asleep that this silly old podcast is worth sponsoring in the future this show is also presented by the great and powerful cash app the number one finance app in the app store when you get it use code lex podcast cash app lets you send money to friends buy bitcoin and invest in the stock market with as little as one dollar it's one of the best designed interfaces of an app that i've ever used to me good design is when everything is easy and natural bad design is when the app gets in the way either because it's buggy or because it tries too hard to be helpful i'm looking at you clippy from microsoft even though i love you anyway there's a big part of my brain and heart that loves to design things and also to appreciate great design by others so again if you get cash out from the app store google play and use the code lex podcast you get ten dollars and cash app will also donate ten dollars to first an organization that is helping to advance robotics and stem education for young people around the world and now here's my conversation with richard carp you wrote that at the age of 13 you were first exposed to plain geometry and was wonder struck by the power and elegance of formal proofs are there problems proofs properties ideas and plain geometry that from that time that you remember being mesmerized by or just enjoying to go through to prove various aspects so michael rabin told me this story about an experience he had when he was a young student who was ex tossed out of his classroom for bad behavior and was wandering through the corridors of his school and came upon two older students who were studying the problem of finding the shortest distance between two non-overlapping circles and michael thought about it and said you take the straight line between the two centers and the segment between the two circles is the shortest because a straight line is the shortest distance between the two centers and any other line connecting the circles would be on a longer line and i thought and he thought and i agreed that this was just elegant that pure reasoning could come up with such a result certainly the the shortest distance from the two centers of the circles is a straight line could you once again say what's the next step in that proof well any any segment joining the the two circles if you extend it by taking the radius on each side you get a segment with a path with three edges which connects the two centers and this has to be at least as long as the shortest path which is the straight line the straight line yeah wow yeah that is that's quite quite simple so what what is it about that elegance that you just find uh compelling well just that you could establish a a fact about geometry beyond dispute by pure reasoning i i also enjoy the challenge of solving puzzles in plain geometry it was much more fun than the earlier mathematics courses which were mostly about arithmetic operations and manipulating them was was there something about geometry itself the slightly visual component of it yes absolutely although i lacked three-dimensional vision i wasn't very good at three-dimensional vision you mean being able to visualize three-dimensional objects three-dimensional objects or or um surfaces hyperplanes and so on um so so there there i didn't have an intuition but for example the fact that the sum of the angles of a triangle is 180 degrees is proved convincingly um and it comes as a surprise that that can be done why is that surprising the the well it is a surprising uh is a surprising idea i suppose uh why is that proved difficult it's not that's the point it's so easy and yet it's so convincing do you remember what is the proof that it's um as up to 180 uh you you start at a corner and draw a line um parallel to the opposite side and that line sort of trisects the angle between the other two sides and uh you you get a uh a half plane which has to add up to 180 degrees and it consists in the angles by by the equality of uh alternate angles what's it called you you you get a correspondence between the angles created by the side along the side of the triangle and the three angles of the triangle has geometry had an impact on when you look into the future of your work with combinatorial algorithms has it had some kind of impact in terms of yeah being able the puzzles the visual aspects that were first so compelling to you not euclidean geometry particularly i think i use tools like linear programming and integer programming a lot and but those require high dimensional visualization and so i tend to go by the algebraic properties um right the you you go by the algebra the linear algebra and not by the the visualization well the interpretation in terms of for example finding the highest point on a polyhedron as in linear programming is motivating but again it i don't have the high dimensional intuition that would particularly inform me so i sort of deep lean on the algebra so to linger on that point what kind of visualization do you like do you do when you're trying to think about we'll get to combinatorial algorithms but just algorithms in general yeah what kind of what what's inside your mind when you're thinking about designing algorithms or or even just tackling any any mathematical problem well i think that usually an algorithm is uh involves a repetition of some inner loop and and so i can sort of visualize the um the distance from the desired solution as iteratively reducing until you finally hit the exact solution and try to take steps that get you closer to the try to take steps that get closer and having the certainty of converging so it's it's racist it's basically the mechanics of the algorithm is often very simple but especially when you're trying something out on the computer so for example i did some work on the traveling salesman problem and i could see there was a particular function that had to be minimized and it was fascinating to see the successive approaches to the minimum to the optimum you mean so first of all traveling salesman problems where you have to visit uh every city without ever the only ones yeah that's right find the shortest path through cities yeah uh which is sort of a canonical standard a really nice problem that's really hard right exactly so can you say again what was nice about the objective being able to think about the objective function there and maximizing it or minimizing it well just that the um as the algorithm proceeded it was you were making progress continual progress and and eventually getting to the optimum point so there's two two parts maybe maybe you can correct me but first is like getting an intuition about what the solution would look like and or even maybe coming up with a solution and two is proving that this thing is actually going to be pretty good uh what part is harder for you where's the magic happen is it in the first sets of intuitions or is it in the detail the messy details of actually showing that it is going to get to the exact solution and it's going to run at this at a certain complexity well the magic is just the fact that it the the gap from the optimum decreases monotonically and you can see it happening and um various metrics of what's going on are improving all along until finally hit the optimum perhaps later we'll talk about the assignment problem and i can illustrate illustrate a little better yeah now zooming out again as you write don knuth has called attention to a breed of people who derive great aesthetic pleasure from contemplating the structure of computational processes so don calls these folks geeks and you write that you remember the moment you realized you were such a person you were shown the hungarian algorithm to solve the assignment problem right so perhaps you can explain what the assignment problem is and what uh the hungarian algorithm is so in the assignment problem you have uh n boys and in girls and you are given the desirability of uh or the cost of matching the i boy with the jth girl for all i and j you're given a matrix of numbers and you want to find the one-to-one matching of the boys with the girls such that the some of the associated costs will be minimized so the the best way to match the boys with the girls or men with jobs or any two sets um no any possible matching is possible or yeah all one-to-one correspondences are permissible if there is a connection that is not allowed then you can think of it as having an infinite cost so um what you do is uh to depend on the observation that the identity of the optimal assignment or as we call it the optimal permutation um is not changed if you subtract a constant from any row or column of the matrix you can see that the comparison between the different assignments is not changed by that um because you're penal if you decrease a particular row all the elements of a row by some constant all solutions decrease by the cost of that by an amount equal to that constant so the idea of the algorithm is to start with a matrix of non-negative numbers and keep subtracting from rows or from our entire columns um in such a way that you subtract the same constant from all the elements of that row or column uh while maintaining the property that um uh all the elements are non-negative simple yeah and so and so um what you have to do is uh is find small moves which will decrease the total cost while subtracting constants from rows or columns and there's a particular way of doing that by computing a kind of shortest path through the elements in the matrix and you just keep going in this way until you finally get a full permutation of zeros while the matrix is non-negative and then you know that that has to be the cheapest is that as simple as it sounds so the the shortest path of the matrix part yeah the simplicity lies in how you find the what i oversimplified slightly what you you you will end up subtracting a constant from some rows or columns and adding the same constant back to other rows and columns so as not to not to reduce any of the zero elements you leave them unchanged but each individual step modifies us several rows and columns by the same amount but overall decreases the cost so there's something about that elegance that made you go aha this is a beautiful like it's it's uh it's amazing that something like this something so simple can solve a problem like this yeah it's really cool if i had mechanical ability i would probably like to do woodworking or other activities where you sort of shape something in into something beautiful and orderly and there's something about the orderly systematic nature of uh that innovative algorithm that is pleasing to me so what do you think about this idea of geeks as don knuth calls them what do you think of is it something uh specific to a mindset that allows you to discover the elegance and computational processes or is this all of us can all of us discover this beauty are you born this way i think so i always like to play with numbers i i i used to amuse myself by multiplying four digit decimal numbers in my head and putting myself to sleep by starting with one and doubling the number as long as i could go and uh testing my memory my ability to retain the information and i also read somewhere that you uh you wrote that you enjoyed uh showing off to your friends by i believe multiplying four digit numbers uh right a couple of four digit numbers yeah i had a summer job at a beach resort outside of boston and uh the other employee i i was the barker at a skee-ball game yeah i used to i used to sit at a microph microphone saying come one come all come in and play ski ball five cents to play nickel to win and so on that's what a barker i was gonna i wasn't sure if i should know but barker that's so you're the the charming outgoing person is getting people to uh come in yeah well i wasn't particularly charming but i could be very repetitious and loud and the other employees were sort of juvenile delinquents who had no academic bent but somehow i found that i could impress them by by performing this mental melter or mental arithmetic you know there's something too that you know one of some of the most popular videos on the internet is uh there's a there's a youtube channel called number file that shows off different mathematical ideas there's still something really profoundly interesting to people about math the the beauty of it something even if they don't understand the basic concept even being discussed there's something compelling to it what do you think that is any lessons you drew from the early teen years when you were showing off to your friends with the numbers like is what is it that attracts us to the beauty of mathematics do you think the general population not just the the computer scientists and math the magicians i think that it you know you can do amazing things you can test whether large numbers are prime you can uh um you can solve little puzzles about cannibals and missionaries and there's a kind of achievement it's it's it's puzzle solving and at a higher level the fact that you can you can do this reasoning that you can prove in an absolutely ironclad way that the some of the angles of a triangle is 180 degrees yeah it's a nice escape from the messiness of the real world where nothing can be proved so and we'll talk about it but sometimes the ability to map the real world into such problems where you can't prove it is this a is a powerful step yeah it's amazing that we can do this another attribute of geeks is they they're not necessarily uh endowed with emotional intelligence so they can live in a world of abstractions without having to uh master the complexities of uh dealing with people so just to link on the historical note as a phd student in 1955 he joined the computational lab at harvard where howard aiken had built the mark 1 and the mark iv computers just to take a step back into that history what were those computers like uh the mark iv filled me a large room much big much bigger than this large office that we were talking in now and you could walk around inside it they were they were rows of relays you could just walk around the interior and uh the machine would sometimes fail because of bugs which literally meant flying creatures landing on the switches so i never i never used that machine for any practical purpose the lab eventually acquired a uh one of one of the earlier um commercial computers this is already in the 60s no in the mid 50s in mid 50s or mid late 50s there was already usual computers in there yeah we had a univac a 2000 univac with 2000 words of storage and so you had to work hard to allocate the memory properly to also the excess time from one word to another depended on the number of the particular words and so you there was an art to sort of arranging the storage allocation to make fetching data rapid were you attracted to this actual physical world implementation of mathematics so it's a mathematical machine that's actually doing the math physically no not at all i think i was a i was attracted to the underlying algorithms so but did you draw any inspiration so could you have imagined like what did you imagine was the future of these giant computers could you imagine that 60 years later would have billions of these computers all over the world i couldn't imagine that but there was a sense in the laboratory that this was the wave of the future in fact my mother influenced me she she told me that data processing was going to be really big and i should get into it she's a smart woman yeah she was a smart woman and there was just a feeling that this was going to change the world but i i didn't think of it in terms of personal computing i hadn't that i had no anticipation that we would be walking around with computers in our pockets or anything like that did you see computers as tools as mathematical mechanisms to analyze sort of sort of theoretical computer science or as the ai folks which is an entire other community of dreamers yeah that's something that could one day have human level intelligence well ai wasn't very much on my radar i did read uh turing's paper about the uh the uh the uh the drawing test computing and intelligence yeah the turing test um what'd you think about that paper was that just like science fiction um i thought that it wasn't a very good test because it was too subjective so i i didn't feel that i didn't feel that the turing test was really the right way to calibrate how intelligent an algorithm could be to linger on that do you think it's pos because you've come up with some incredible tests later on tests on algorithms right yeah that are like strong reliable robust across a bunch of different classes of algorithms but returning to this emotional mess that is intelligence do you think it's possible to come up with the test that's as iron-clad as some of the computational complexity work well i think the greater question is whether it's possible to achieve human level level intelligence right so that's so first of all let me at the philosophical level do you think it's possible to create algorithms that reason and would seem to us to have the same kind of intelligence as human beings it's an open question um it seems to me that um most of the achievements have acquire operate within a very limited set of ground rules and for a very limited precise task which is a quite different situation from the processes that go on in the minds of humans which where they have to sort of function in changing environments they have emotions they have [Music] um physical attributes for acquire for exploring their environment um they have intuition they have desires um emotions and i don't see anything in the current achievements of what's called ai that come close to that capability i don't think there's any computer program which surpasses a six-month-old child in terms of comprehension of the world do you think this complexity of human intelligence all the cognitive abilities we have all the emotion do you think that could be reduced one day or just fundamentally can it be reduced to an out a set of algorithms or an algorithm so can a touring machine achieve human level intelligence i am doubtful about that i guess the argument in favor of it is that the human brain seems to achieve what we call intelligence cognitive abilities of different kinds and if you buy the premise that the human brain is just an enormous interconnected set of switches so to speak then in principle you should be able to diagnose what that interconnection structure is like characterize the individual switches and build a simulation outside but why that may be true in principle that cannot be the way we're eventually going to tackle this problem it's you know you know that that does not seem like a feasible way to go about it so it there is however an existence proof that um uh if you believe that the brain is is just a network of of neurons operating by rules i guess you could say that that's an existence proof of the ability to build the capabilities of a mechanism um but it would be almost impossible to acquire the information unless we got enough insight into the operation of the brain but there's so much mystery there do you think what do you make of consciousness for example there's something as an example of something we completely have no clue about the fact that we have this subjective experience right is it possible that this network of uh this circuit of switches is able to create something like consciousness to know its own identity yeah to know to know the algorithm to know itself to know itself i think if you try to define that rigorously you'd have a lot of trouble yeah that's interesting so i know that there are many who um believe that general intelligence can be achieved and there are even some who are feel certain that uh the singularity will come and uh we will be surpassed by the machines which will then learn more and more about themselves and reduce humans to an inferior breed i am doubtful that this will ever be achieved just for the fun of it could you linger on why what's your intuition why you're doubtful so there are quite a few people that are extremely worried about this uh existential threat of artificial intelligence of us being left behind by the super intelligent new species what's your intuition why that's not quite likely just because none of the achievements in speech or robotics or natural language processing or creation of flexible computer assistance or any of that comes anywhere near close to that level of cognition what do you think about ideas as a sort of uh if we look at moore's law and exponential improvement uh to allow us to that would surprise us sort of our intuition fall apart with with exponential improvement because i mean we're not able to kind of we kind of think in linear improvement yeah we're not able to imagine a world that goes from the mark one computer to a an iphone 10. yeah so do you think it would be we could be really surprised by the exponential growth or or on the flip side is is it possible that also intelligence is actually way way way way harder even with exponential improvement to be able to crack i don't think any constant factor improvement could could change things and given given our current comprehension of how the of of what cognition requires it seems to me that multiplying the speed of the switches by a factor of a thousand or a million uh will not be useful until we really understand the organizational principle behind the network of switches well let's jump into the network of switches and talk about combinatorial algorithms if we could let's step back with the very basics what are combinatorial algorithms and what are some major examples of problems they aim to solve a combinatorial algorithm is is one which deals with a a system of discrete objects that can occupy various states or take on various values from a discrete set of values um and need to be arranged or or selected um in such a way as to achieve some to minimize some cost function or to prove or to prove the existence of some combinatorial so an example would be um coloring the vertices of a graph what's a graph let's step back so what uh and it's fun to uh to ask one of the greatest computer scientists of all time the most basic questions in the beginning of most books but for people who might not know but in general how you think about it what is what is a graph uh a graph that's that's simple it's a set of points certain pairs of which are joined by lines called edges and they sort of represent the in different applications represent the interconnections between discrete objects so they could be the interactions interconnections between switches in a digital circuit or interconnections indicating the communication patterns of a human community um and they could be directed or undirected and then as you've mentioned before might have costs right they can be directed or undirected they can be you can think of them as if if you think if a graph were representing a communication network then the edge could be undirected meaning that information could flow along it in both directions or it could be directed with only one-way communication a road system is another example of a graph with weights on the edges and then a lot of problems of optimizing the efficiency of such networks or learning about the performance of such networks um uh are the the objective combinatorial algorithm so it could be scheduling classes at a school where the the vertices the nodes of the network are the individual classes and uh the edges indicate the constraints which say that certain classes cannot take place at the same time or certain teachers are available only at cert for certain classes etc or um i talked earlier about the assignment problem of matching the boys with the girls um where um you have a very graph with an edge from each boy to each girl with a weight indicating the cost or in logical design of computers you might want to find a set of so-called gates switches that perform logical functions which can be interconnected to realize some function so you you might ask um how many gates do you need in order to um for for a circuit to give a yes output if at least a given number of its inputs are ones and no if not a few are are present my favorite is probably all the all the work with network flows so anytime you have uh i don't know why it's so compelling but there's something just beautiful about it it seems like there's so many applications and communication networks in uh traffic right flow that you can map into these and then you can think of pipes and water going through pipes and you could optimize it in different ways there's something always visually and intellectually compelling to me about it and of course you've done work there yeah yeah so so there the edges represent channels along which some commodity can flow it might be gas it might be water it might be information maybe supply chain as well like products being products flowing from one operation to another and the edges have a capacity which is the rate at which the commodity can flow and a central problem is to determine given a network of these channels in this case the edges are communication channels the the challenge is to find the maximum rate at which the information can flow along these channels to get from a source to a destination and that's a that's a fundamental combinatorial problem that i i've worked on jointly with the scientist jack edmunds we i think we're the first to give a formal proof that this maximum flow problem through a network can be solved in polynomial time which uh i remember the first time i learned that just learning that in um maybe even grad school i don't think it was even undergrad no algorithm yeah do netfl network flows get taught in in um basic algorithms courses yes probably okay so yeah i've i remember being very surprised that max flow is a polynomial time algorithm yeah that there's a nice fast algorithm that solves max flow but so there is an algorithm named after you an admins they haven't carp algorithm for max flow so what was it like tackling that problem and trying to arrive at a polynomial time solution and maybe you can describe the algorithm maybe you can describe what's the running time complexity that you showed yeah well first of all what is a polynomial time algorithm yeah perhaps we could discuss that so yeah let's let's actually just even yeah that's what is algorithmic algorithmic complexity what are the major classes of algorithm complexity so we in in a problem like the assignment problem or scheduling schools or any of these applications um you have a set of input data which might for example be um a set of vertices connected by edges with being you're given for each edge the capacity of the edge and you have algorithms which are think of them as computer programs with operations such as addition subtraction multiplication division comparison of numbers and so on and you're trying to construct an algorithm based on those operations which will determine in a minimum number of computational steps the answer to the problem in this case the computational step is one of those operations and the answer to the problem is let's say the um the configuration of the network that carries the maximum amount of flow and an algorithm is said to run in polynomial time if as a function of the size of the input the number of vertices the number of edges and so on the number of basic computational steps grows only as some fixed power of that size a linear algorithm would execute a number of steps linearly proportional to the size quadratic algorithm would be steps proportional to the square of the size and so on and algorithms that whose running time is bounded by some fixed power of the size are called polynomial algorithms and that's supposed to be relatively fast class of algorithms that's right we theoreticians take that to be the definition of an algorithm being um efficient and and we're interested in which problems can be solved by such efficient algorithms one can argue whether that's the right definition of efficient because you could have an algorithm whose running time is the ten thousandth power of the size of the input and that wouldn't be really efficient and in practice it's oftentimes reducing from an n squared algorithm to an n log n or a linear time is practically the jump that you want to make to allow a real world system to solve a problem yeah that's also true because especially as we get very large networks the size can be in the millions and uh and then anything above uh n log n where n is the size would be uh too much for a practical solution okay so that's polynomial time algorithms what other classes of algorithms are there what's so that usually they they designate polynomials of the letter p yeah there's also np np complete and be hard yeah so can you try to disentangle those and by trying to define them simply right so a polynomial time algorithm is one which was running time is bounded by a polynomial and the size of the input uh there's then there's that the class of such algorithms is called p in the worst case by the way we should say right yeah for every case of the problem and that's very important that in this theory when we measure the complexity of an algorithm we really measure the number of step the growth of the number of steps in the worst case so you may have an algorithm that [Music] runs very rapidly in most cases but if there is any case where it gets into a very long computation that would increase the computational complexity by this measure and that's a very important issue because there as we may have discussed later there are some very important algorithms which don't have a good standing from the point of view of their worst case performance and yet are very effective so so theoreticians are interested in p the class of problem solvable in polynomial time then there's np which is the class of problems which may be hard to solve but where the where when confronted with the solution you can check it in polynomial time let me give you an example there so if we look at the assignment problem uh so you have uh n boys you have n girls you the number of numbers that you need to write down to specify the problem instances n squared and the question is how many steps are needed to solve it and jack edmonds and i were the first to show that it could be done in time n cubed uh earlier algorithms required n to the fourth so as a polynomial function of the size of the input this is a fast algorithm now to illustrate the class np the question is how long would it take to verify that a solution is optimal so for example if if the input was a graph we might want to find the largest clique in the graph or a clique is a set of vertices such that any vertex each vertex in the set is adjacent to each of the others so the clique is a complete subgraph yeah so if it's a facebook social network everybody's friends with everybody else it's close click no that would be what's called a complete graph it would be no i mean uh within that click uh within that clique yeah yeah they're all friends so a complete graph is when everybody is friendly as everybody is friends with everybody yeah so the problem might be to determine whether in a given graph there exists a clique of a certain size well that turns out to be a very hard problem but how but if somebody hands you a clique and asks you to check whether it is a hands you a set of vertices and ask you to check whether it's a clique you could do that simply by exhaustively looking at all of the edges between the vertices and the clique and verifying that they're all there and that's a polynomial time that's a polynomial so the verify there the problem of finding the clique appears to be extremely hard but the problem of verifying a clique to see if it reaches the target number of vertices is easy to solve is easy to verify so finding the clique is hard checking it is easy problems of that nature are called the non-deterministic polynomial time algorithms and that's the class np and what about mp complete and be hard okay let's talk about problems where you're getting a yes no a yes or no answer rather than a numerical value so either there is a a perfect matching of the of the boys with the girls or there isn't it's clear that um every problem in p is also in np if you can solve the problem exactly then you can certainly verify the solution on the other hand there are problems in the class np this is the class of problems that are easy to check although they may be hard to solve it's not at all clear that problems in np lie in p so for example if we're looking at scheduling classes at a school the fact that you can verify when handed a schedule for the school whether it meets all the requirements that doesn't mean that you can find the schedule rapidly so intuitively np non-deterministic polynomial checking rather than finding is going to be harder than is going to include is easier checking is easier and therefore the class of problems that can be checked appears to be much larger than the class of problems that can be solved and then you keep adding appears to and uh sort of these uh additional words that designate that we don't know for sure yet we don't know for sure so the theoretical question which is considered to be the most central problem in theoretical computer science or at least computational complexity theory combinatorial algorithm theory the question is whether p is equal to np if p were equal to np it would be amazing it would mean that every problem where a solution can be rapidly checked can actually be solved in polynomial time we don't really believe that's true if you're scheduling classes at a school it's we expect that if somebody hands you a satisfying schedule you can verify that it works that doesn't mean that you should be able to find such a schedule so intuitively np encompasses a lot more problems than p so can we take a small tangent and break apart that intuition so do you first of all think that the biggest sort of open problem in computer science maybe mathematics is whether p equals np do you think p equals np or do you think p is not equal to np if you had to bet all your money on it i would bet that p is unequal to np uh simply because there are problems that have been around for centuries and have been studied intensively in mathematics and even more so in the last 50 years since the p versus np was stated and no polynomial time algorithms have been found for these easy to check problems so one one example is a problem that goes back to the mathematician gauss who is interested in um factoring large numbers so uh we know what a number is prime if it doesn't if it cannot be written as the product of two or more numbers unequal to one uh so if we can factor the a number like 91 that's 7 times 13 but if i give you 20 digit or 30 digit numbers you're probably going to be at a loss to have any idea whether they can be factored so the pr the problem of factoring very large numbers is does not appear to have an efficient solution but once you have found the factors express the number as a product the two smaller numbers you can quickly verify that they are factors of the number and your intuition is a lot of people finding you know this a lot of brilliant people have tried to find algorithms for this one particular problem there's many others like it that are really well studied and it would be great to find an efficient algorithm for right and in fact we have some results that i was instrumental in obtaining following up on work by the mathematician stephen cook to show that within the class np of easy to check problems there's a huge number that are equivalent in the sense that either all of them or none of them lie in p and this happens only if p is equal to np so if p is unequal to np we would also know that virtually all the standard combinatorial problems if p is unequal to np none of them can be solved in polynomial time can you explain how that's possible to tie together so many problems in a nice bunch that if one is proven to be efficient then all are the first and most important stage of progress was a result by stephen cook who showed that a certain problem called the satisfiability problem of propositional logic is as hard as any problem in the class p so the propositional logic problem is expressed in terms of expressions involving the logical operations and or and not offering operating operating on variables that can be either true or false so an instance of the problem would be some formula involving and or and not and the question would be whether there is an assignment of truth values to the variables in the problem that would make the formula true so for example if i take the formula a or b and a or not b and not a or b and not a or not b and take the conjunction of all four of those so-called expressions you can determine that no assignment of truth values to the variables a and b will allow that conjunction of cl what are called clauses uh to be true so that's an example of a formula in propositional logic involving expressions based on the operations and or and not um that's an example of a problem which has which is not satisfiable there is no solution that satisfies all of those constraints and that's like one of the cleanest and fundamental problems in computer science it's like a nice statement of a really hard problem it's a nice statement a really hard problem and and what cook showed is that every problem in np is can be re-expressed as an instance of the satisfiability problem so to do that he used the observation that a very simple abstract machine called the turing machine can be used to describe any algorithm an algorithm for any realistic computer can be translated into an equivalent algorithm on one of these turing machines which are extremely simple it's a tour machine there's a tape and you can yeah you have to walk along that data on a tape and you have basic instructions a finite list of instructions which say we would say if you're reading a particular symbol on the tape and you're in a particular state then you can move to a different state and change the state of the number that you or the element that you were looking at the cell of the tape that you were looking at and that was like a metaphor and a mathematical construct that touring put together to represent all possible computation all possible computation now one of these so-called turing machines is too simple to be useful in practice but for theoretical purposes we can depend on the fact that an algorithm for any computer can be translated into one that would run on a turing machine right and then using that fact um he could sort of describe any possible nondeterministic polynomial time algorithm any pro any algorithm for a problem in np could be expressed as a sequence of moves of the turing machine described in terms of reading a symbol on the tape while you're in a given state and moving to a new state and leaving behind a new new symbol and given that the fact that any non-deterministic polynomial time algorithm can be described by a list of such instructions you could translate the problem into the language of the satisfiability problem is that amazing to you by the way if you take yourself back when you were first thinking about the space of problems is that how amazing is that it's astonishing when you look at cook's proof it's not too difficult to sort of figure out why this is why this is so but the implications are staggering it tells us that this of all the problems in np all the problems where solutions are easy to check they can they can all be rewritten in terms of the satisfiability problem yeah it's a in adding so much more weight to the p equals np question because all it takes is to show that one that's right one algorithm in this class so the p versus np can be re-expressed is simply asking whether the satisfiability problem of propositional logic you'll solve a billion polynomial time but there's more uh i i encountered cook's paper when he published it in a conference in 1971. yeah so when i saw uh cook's paper and saw this uh reduction event of all of each of the problems in np by a uniform method to to the satisfiability problem of propositional logic that meant that the satisfiability problem was a universal combinatorial problem and it occurred to me through experience i had had in trying to solve other combinatorial problems that there were many other problems which seemed to have that universal structure and so i began looking for reductions from the satisfiability to other problems one of the other problems would be the so-called integer programming problem of solving a determining whether there's a solution to a um a set of linear inequalities involving integer variables just like linear programming but there's a constraint that the variables must remain integers integers in fact must be either zero or one because they could only take on those values and that makes the problem much harder yes that makes the problem much harder and it was not difficult to show that the satisfiability problem can be restated as an integer programming problem so can you pause on that was that one of the first problem mappings that you try to do and how hard is that map you said it wasn't hard to show but you know that's a that's a big leap it is a big leap yeah well let me let me give you another example um another problem in np is whether a graph contains a clique of a given size and now the question is can we reduce the propositional logic problem to the problem of whether there's a clique of a certain size well if you look at the propositional logic problem it can be expressed as a number of clauses each of which is a of the form a or b or c where a is either one of the variables in the problem or the negation of one of the variables and the an instance of the propositional logic problem can be rewritten using operations of boolean logic can be re rewritten as the conjunction of a set of clauses the and of a set of ors where each clause is a disjunction an or of variables or negated variables so the pro the question of uh the in the satisfiability problem is whether those clauses can be simultaneously satisfied now to satisfy all those clauses you have to find one of the terms in each clause which is going to be given that which is going to be true in your truth assignment but you can't make the same variable both true and false so if you have the variable a in one clause and you want to satisfy that clause by making a true you can't also make the complement of a true in some other clause and so the goal is to make every single clause true if it's possible to satisfy this and the way you make it true is at least one term in the clause must be it must be true so so now we uh to convert this problem to something called the independent set problem where you're just sort of asking for a set of vertices in a graph such that no two of them are adjacent sort of the opposite of the clique problem so we've seen that we can now express that as finding a set of terms one in each clause without picking both the variable and the negation of that variable because you if the variable is assigned the truth value the negated variable has to have the opposite truth value right and so we can construct the graph where the vertices are the terms in all of the clauses and you have an edge between two terms if um if an edge between two occurrences of terms if they're both in the same clause because you're only picking one element from each clause and also an edge between them if they represent opposite values of the same variable because you can't make a variable both true and false and so you get a graph where you have all of these occurrences of variables you have edges which which mean that you're not allowed to choose both ends of the edge either because they're in the same clause or they're con negations of one another all right and that's uh first of all sort of to zoom out that's a really powerful idea that you can take a graph and connect it to a logic equation right somehow and do that mapping for all possible formulations of a particular problem on a graph yeah i mean that that still is hard for me to believe that that's possible that that they're like what do you make of that that um there's such a union of there's such a friendship among all these problems across that somehow are akin to combinatorial uh algorithms that they're all somehow related yeah i i know it can be proven yeah but what do you make of it that that that's true well if they just have the same expressive power you can take any one of them and translate it into the terms of the other you know the fact that they have the same expressive power also somehow means that they can be translatable right and what i did in the 1971 paper was to take 21 fundamental problems commonly occurring problems of packing covering matching and so forth or lying in the class np and show that the satisfiability problem can be re-expressed as any of those that any of those have the same expressive proper uh expressive power so and that was like throwing down the gauntlet of saying there's probably many more problems like this right but that's just saying that look that they're all the same they're all the same but not exactly yeah yeah they're all the same in terms of whether they are um rich enough to express any of the others but that doesn't mean that they have the same computational complexity but what we can say is that either all of these problems or none of them are solvable in polynomial time yeah so where does np completeness and np hard classes well that's just a small technicality so when we're talking about decision problems that means that the answer is just yes or no there is a clique of size 15 or there's not a clique of size 15. on the other hand an optimization problem would be asking find the largest clique the answer would not be yes or no it would be 15. so um so when you're asking for the when you're putting a valuation on the different solutions and you're asking for the one with the highest valuation that's an optimization problem and there's a very close affinity between the two kinds of problems but the counterpart of being the hardest decision problem the hardest yes no problem the kind of part of that uh is is to minimize or maximize an objective function and so a problem that's hardest in the class when viewed in terms of optimization those are called np-hard rather than np-complete and np-complete is for decision problems and np-complete is for decision problems so if somebody shows that p equals np what do you think that proof will look like if you were to put on yourself if it's possible to show that as a proof or to demonstrate an algorithm all i can say is that it will involve concepts that we do not now have and approaches that we don't have do you think those concepts are out there in terms of inside complexity theory inside of computational analysis of algorithms do you think there's concepts that are totally outside of the box that we haven't considered yet i think that if there is a proof that p is equal to np or that p is not equal to np uh it'll depend on concepts that are now outside the box now if that's shown either way p equals np or p not well actually p equals np what impact you kind of mentioned a little bit but can you can you linger on it what kind of impact would it have on theoretical computer science and perhaps software these systems in general well i think it would have enormous impact on the on the world any in either way case if p is unequal to np which is what we expect then we know that we're in that for the great majority of the combinatorial problems that come up since they're known to be np complete uh we're not going to be able to solve them by efficient algorithms however there's a little bit of hope in that it may be that we can solve most instances all we know is that if a problem is not in p then then it can't be solved efficiently on all instances um but but basically it will um it will if we find that p is unequal to np it will mean that we can't expect always to get the optimal solutions to these problems and we have to depend on heuristics that perhaps work most of the time or give us good approximate solutions but not so we would turn our eye towards the heuristics with a little bit more um acceptance and comfort on our hearts exactly okay so let me ask a romanticized question what to you is one of the most or the most beautiful combinatorial algorithm in your own life or just in general in the field that you've ever come across or have developed yourself oh i like the stable matching problem or the stable marriage problem uh very much what's the stable matching problem yeah imagine that you want to marry off n boys with uh and girls and each boy has an ordered list of his preferences among the girls his first choice is second choice through her nth choice and um each girl also has a an ordering of the boys first choice second choice and so on and we'll say and we will say that a matching one-to-one matching of the boys with the girls is stable if there are no two couples in the matching such that the boy in the first couple prefers the girl in the second couple to her mate and she refers the boy to her current mate in other words if there is the matching is stable if there is no pair who want to run away with each other leaving their partners behind gosh yeah uh yeah actually this is relevant to matching uh uh residents with hospitals and some other real life problems although not quite in the form that i described so it turns out that there is that a stable for any set of preferences a stable matching exists and um moreover it can be computed by a simple algorithm in which each boy starts making proposals to girls and if the girl receives the proposal she accepts it tentatively but she can drop it if she can end it she can drop it later if she gets a better proposal from her point of view and the boys start going down their lists proposing to their first second third choices until stopping when a proposal is accepted but the girls meanwhile are watching the proposals that are coming into them and the girl will drop her current partner um if she gets a better proposal and the boys never go back through they they never go back yeah so once they've been denied they don't try again they don't they don't they don't try again because the girls are always improving their status as they get more as they receive better and better proposals the boys are going down their list starting with their top preferences and um one can prove that that the process will come to an end where everybody will get matched with somebody and you'll you won't have any pair that want to abscond from each other do you find the proof or the algorithm itself beautiful or is it the fact that with the the simplicity of just the two marching i mean the simplicity of the underlying rule of the algorithm is that the beautiful part both i i would say um and you also have the observation that you might ask who is better off the boys who are doing the proposing or the girls who are reacting to proposals and it turns out that it's it's the boys who are doing the doing the best that is each boy is doing at least as well as uh he could do in any other stable matching so there's a sort of lesson for the boys that you should go out and be proactive and make those proposals go for broke yeah i don't know if the this is directly mappable philosophically to our society but uh certainly seems like a compelling notion and like you said there's probably a lot of actual real world problems that this could be mapped to yeah well you get you you get complications for example what happens when a husband and wife want to be assigned to the same hospital so you you have to take those constraints into account and then the problem becomes np hard or uh why is it a problem for the husband and wife to be assigned to the same hospital no it's desirable so desirable or at least go to the same city so you can't if you're i think if you're assigning residents to hospitals and then you have some preferences uh for the husband and wife for for the hospitals the residents have their own preferences references residents both male and female have their own preferences um the hospitals have their preferences but if if resident a the boy is going to philadelphia then you'd like his wife be also to be assigned to a hospital in philadelphia so which step makes it a and be hard problem do you mention the fact that you have this additional constraint that it's not just the preferences of individuals but the fact that the two partners to a marriage have to go to have to be assigned to the same place i'm being a little dense uh the sort of the perfect matching no not the stable matching is what you refer to that's when two partners are trying to okay what's confusing you is that in the first interpretation of the problem i had boys matching with girls yes in the second interpretation you have humans matching with institutions i and there's a coupling between within the gotcha within the humans any added little constraint will make it an empty heart problem well yeah okay by the way the algorithm you mentioned wasn't was one of yours no no that was due to gail and shapley and uh my friend david gale passed away before he could get part of the nobel prize but his partner shapley shared in a nobel prize with somebody else for economics for huma for economics uh for ideas stemming from this stable matching idea so you've also have developed yourself some elegant beautiful algorithms again picking your children so the the the robin carp algorithm for string searching pattern matching admin carb algorithm for max flows we mentioned hop craft carbon algorithm for finding maximum cardinality matchings and bipartite graphs is there ones that stand out to you as ones you're most proud of or just um whether it's beauty elegance or just being the right discovery development in your life that you're especially proud of i like the raven carp algorithm because it illustrates the power of randomization so the the problem there is to um is to decide whether uh a given long string of symbols from some alphabet contains a given word whether a particular word occurs within some very much longer word and so the the idea of the algorithm is to associate with the word that we're looking for a fingerprint some some number or some combinatorial object that describes that word and then to look for an occurrence of that same fingerprint as you slide along the longer word and what we do is we associate with each word a number so we first of all we think of the letters that are kind of occur in a word as the digits of let's say decimal or whatever base your whatever number of different symbols there are that's the base of the of the numbers yeah right so every word can then be thought of as a number with the letters being the digits of that number and then we pick a random prime number in a certain range and we take that word viewed as a number and take the remainder on dividing the dividing that number by the prime so coming up with a nice hash function it's a it's a kind of hash function yeah um it gives you a little little shortcut for for that particular word yeah that so that's the that's the uh it's very different than the any and other algorithms of its kind that we're trying to do search uh string matching yeah which usually are combinatorial and don't involve the idea of taking a random fingerprint yes and doing the fingerprinting has two advantages one is that as we slide along the long word digit by digit we can we we keep a window of of a certain size the size of the word we're looking for and we compute the fingerprint of every stretch of that length and it turns out that just a couple of arithmetic operations will take you from the fingerprint of one part to what you get when you slide over by one position so the computation of all the fingerprints is um simple and secondly it's unlikely if the prime is chosen randomly from a certain range that you will get two of the segments in question having the same fingerprint right and so there's a small probability of error which can be checked after the fact and also the ease of doing the computation because you're working with these fingerprints which are remainders modulo some big prime so that's the magical thing about randomized algorithms is that if you add a little bit of randomness it somehow allows you to take a pretty naive approach a simple looking approach and allow it to run extremely well so can you maybe take a step back and say like what is a randomized algorithm this category of algorithms well it's um just the ability to draw a random number from such um from some range or to to associate a random number with some object or to draw fro at random from some set so another example is very simple if we're conducting a presidential election and we would like to pick the winner in principle we could draw a random sample of all of the voters in the country and if it was a side of substantial size say a few thousand then the most popular candidate in that group would be very likely to be the correct choice that would come out of counting all the millions of votes of course we can't do this because first of all everybody has to feel that his or her vote counted and secondly we can't really do a purely random sample from that population and i guess thirdly there could be a tie in which case we wouldn't have a significant difference between two candidates but those things aside if you didn't have all that messiness of human beings you could prove that that kind of random picking would be just that random picking would would be would solve the problem with a very with a very low probability of error another example is testing whether a number is prime so if i want to test whether [Music] 17 is prime i could pick any number between 1 and 17 and raise it to the 16th power modulo 17 and you should get back the original number that's a famous formula due to ferma about it's called fairmont's little theorem that if you take any a any number a in the range 0 through n minus 1. and raise it to the n minus one paper uh power modulo n you'll get back the number a if the number is if a is prime yeah so if you don't get back the number a that's a proof that a number is not prime well and you can show that um suitably define the the the probability that you will get a value unequal you will get a violation of fermat's result is very high and so this gives you a way of rapidly proving that a number is not prime it's a little more complicated than that because uh there are certain values of n where something a little more elaborate has to be done but that's the basic idea using taking an identity that holds for primes and therefore if it ever fails on any instance for a non-prime unit you know that the number is not prime it's a quick joy a fast choice fast proof that a number is not prime can you maybe elaborate a little bit more what's your intuition why randomness works so well and results in such simple algorithms well uh the example of conducting an election where you could take in in theory you could take a sample and depend on the validity of the sample to really represent the whole is a just the basic fact of statistics which gives a lot of opportunities um and i actually exploited that sort of random random sampling idea in uh designing an algorithm for counting the number of solutions that satisfy a particular formula and propositional calc propositional particular so some some some uh version of the satisfiability problem or a version of the satisfiability problem is there some interesting insight that you want to elaborate on like what some aspect of that algorithm that might be useful to describe so you you have a a collection of formulas and you want to count the number of solutions that satisfy at least one of the formulas and you can count the number of solutions that satisfy any particular one of the formulas but you have to account for the fact that that solution might be counted many times if it solves more than one of the formulas and so what what you do is you sample from the formulas according to the number of solutions that satisfy each individual one in that way you draw a random solution but then you correct by looking at the number of formulas that satisfy that random solution and uh and don't double count so if if you you can think of it this way so you have a matrix of zeros and ones and you want to know how many columns of that matrix contain at least one one and you can count in each row how many ones there are so what you can do is draw from the rows according to the number of ones if a row has more ones it gets to run more frequently but then if you draw from that row you have to go up the column and looking at where that same one is repeated in different rows and only count it as a success or a hit if it's the earliest row that contains the one right and that gives you a robust statistical estimate of the total number of columns that contain at least one of the ones so that that is an example of the same principle that was used in studying random sampling another viewpoint is that if you have a phenomenon that occurs almost all the time then if you sample one of the occasions where it occurs you're most likely to and you're looking for an occurrence a random occurrence is likely to work so that comes up in solving identities solving algebraic identities you you get um two formulas that may look very different you want to know if they're really identical what you can what you can do is just pick a random value and evaluate the formulas at those two at that value and see if they seeing if they agree and you depend on the fact that if the formulas are distinct then they're going to disagree a lot and so therefore a random choice will exhibit the disagreement if there are many ways for the two to disagree and you only need to find one disagreement then random choice is likely to yield it and in general so we've just talked about randomized algorithms but we can look at the probabilistic analysis of algorithms and that gives us an opportunity to step back and as we said everything we've been talking about is worst case analysis right could you maybe comment on the usefulness and the power of worst case analysis versus best case analysis average case probabilistic how do we think about the future of theoretical computer science computer science in the kind of analysis we do of algorithms does worst case analysis still have a place an important place or do we want to try to move forward towards kind of average case analysis yeah and what what are the challenges there so if worst case analysis shows that an algorithm is always good that's fine if worst case analysis uh is used to show that the problem that the solution is not always good then you have to step back and do something else to ask how often will you get a good solution just to pause on that for a second that that's so beautifully put because i think we tend to judge algorithms we throw them in the trash the moment their their worst case is shown to be bad right and and and that's unfortunate i think we use a good example is um going back to the satisfiability problem there are very powerful programs called set solvers which in practice fairly reliably solve instances with many millions of variables that arise in a digital design or improving programs correct and other applications and so in in many application areas even though satisfiability as we've already discussed is npe complete the sat solvers will work so well that the people in that discipline tend to think of satisfiability as an easy problem so in other words just for some reason that we don't entirely understand the instances that people formulate in designing digital circuits or other applications are such that satisfiability is not hard to check and even searching for a satisfying solution can be done efficiently in practice and there are many examples for example we talked about the traveling salesman problem so just to refresh our memories uh the problem is you've got a set of cities you have pairwise distances between cities um and you want to find a tour through all the cities that minimizes the total the total cost of all the edges traversed all all the trips between cities the problem is np hard but people using integer programming codes together with some other mathematical tricks solve geometric instances of the problem where the cities are let's say points in the plane uh and get optimal solutions to problems with tens of thousands of cities actually it'll take a few computer months to solve a problem of that size but for problems of size a thousand or two it'll rapidly get optimal solutions provably optimal solutions even though again we know that it's unlikely that the traveling salesman problem can be solved in polynomial time are there methodologies like rigorous systematic methodologies for you said in practice in practice this algorithm is pretty good are there systematic ways of saying in practice this sounds pretty good so in other words average case analysis or you've also mentioned that average case kind of requires you to understand what the typical cases typical instances and that might be really difficult that's very difficult so after i did my original work on getting uh showing all these problems to be np complete i looked around for a way to get some shed some positive light on combinatorial algorithms and what i tried to do was to study problems behavior on the average or with high probability but i had to make some assumptions about what what's the probability space what's the sample space what do they what do we mean by typical problems that's very hard to say so i took the easy way out and made some very simplistic assumptions so i assumed for example that if we were generating a graph with a certain number of vertices and edges then we would generate the graph by simply choosing one edge at a time at ran at random until we got the right number of edges that's that's a particular model of random graphs that has been studied mathematically a lot and within that model i i could prove all kinds of wonderful things i and others who also worked on this so we could show that we know exactly how many edges there have to be in order for um there be a so-called hamiltonian circuit that's a cycle that visits each vertex exactly once we know that if the number of edges is a little bit more than n log n where n is the number of vertices then where such a cycle is very likely to exist and we can give a heuristic that will find it with her high probability and we got a the community in which i was working got a lot of results along these lines but the field tended to be rather lukewarm about accepting these results as meaningful because we were making such a simplistic assumption about the kinds of graphs that we would be dealing with so we could show all kinds of wonderful things it was a great playground i enjoyed doing it but after a while i concluded that um that it didn't have a lot of bite in terms of the practical application oh the okay so there's too much into the world of toy problems yeah that can okay but all right so but is is there a way to find nice representative real world impactful instances of a problem on which demonstrate that an algorithm is good so this is kind of like the machine learning world that's kind of what they at his best tries to do is find a data set from like the real world and show the performance all the all the conferences are all focused on beating the performance of on that real world data set is there an equivalent in complexity analysis not really um don knuth started to collect examples of graphs coming from various places so he would have a whole zoo of different graphs that he could choose from and he could study the performance of algorithms on different types of graphs and um but there it's really important and compelling to be able to define a class of graphs so that the the actual act of defining a class of graphs that you're interested in it seems to be a non-trivial step if we're talking about instances that we should care about in the real world yeah it's there's nothing available there that would be analogous to the training set for supervised learning you know where you sort of assume that the world has given you a bunch of examples to work with we don't really have that for problems for combinatorial problems on graphs and networks you know there's been a huge growth a big growth of data sets available do you think some aspect of theoretical computer science i might be contradicting my own question while saying it but will there be some aspect an empirical aspect of theoretical computer science which will allow the fact that these datasets are huge we'll start using them for analysis sort of you know if you want to say something about a graph algorithm you might take a net a social network like facebook and looking at subgraphs of that and prove something about the facebook graph and be respected and at the same time be respected in the theoretical computer science community that hasn't been achieved yet i'm afraid is that is that uh is it p equals np is that impossible is is it impossible to publish a successful paper in the theoretical computer science community that shows some some performance on a real-world data set or is that really just those are two different worlds well they haven't really come together i would say that there is a field of experimental algorithmics where people sometimes are given some family of examples sometimes they just generate them at random and they report on performance but there's no convincing evidence that the sample is representative of anything at all so let me ask in terms of breakthroughs and open problems what are the most compelling open problems to you and what possible breakthroughs do you see in the near term in terms of theoretical computer science well there are all kinds of relationships among complexity classes that can be studied just to mention one thing i wrote a paper with richard lipton in 1979 where we asked the following question um if you take a problem a combinatorial problem in np let's say and you um choose a and you pick the the size of the problem uh say it's a traveling salesman problem but of size 52 and you ask could you get an efficient a small boolean circuit tailored for that size 52 where you could feed the edges of the graph in in as boolean inputs and get as an output the question of whether or not there's a tour of a certain length and that would in other words briefly what you would say in that case is that the problem has small circuits polynomial size circuits now we know that if p is equal to np then in fact these problems will have small circuits but what about the converse could a problem have small circuits meaning that it's that an algorithm tailored to any particular size could work well and yet not be a polynomial time algorithm that is you couldn't write it as a single uniform algorithm good for all sizes just to clarify small circuits for problem of particular size or even further constraint small circuit for a particular for no for all the inputs of that cell almost that size is that a trivial problem for a particular instance of so coming up an automated way of coming up with a circuit i guess that's that would be that would be hard yeah but you know but there's the existential question everybody talks nowadays about every existential questions existential challenges yeah you could ask the question [Music] does the hamiltonian circuit problem have a small circuit for for every size for each size a different small circuit in other words could you tailor solutions depending on the size and and get polynomial size even if p is not equal to np right and that would be fascinating if that's true yeah what we proved is that if that were possible then something strange would happen in complexity theory some level uh class which i could briefly describe um something strange would happen so um i'll take a stab at describing what i mean let's go there so we have to define this hierarchy in which the first level of the hierarchy is p and the second level is np and what is np np involves statements of the form there exists a something such that something holds um so for example um um there exists the coloring such that a graph can be colored with only that number of colors or there exists a hamiltonian circuit there's a statement about this graph yeah so so the um np um nnp deals with statements of that kind that there exists a solution now you could imagine a more complicated expression which which says um uh for all x there exists a y such that some uh proposition holds involving both x and y so that would say for example in game theory for all strategies for the first player there exists a strategy for the second player such that the first player wins that would be that would be at the second level of the hierarchy the third level would be there exists an a such that for all b there exists a c that something holds and you can imagine going higher and higher in the hierarchy and you'd expect that the class the complexity class the classes that correspond to those different cases would get bigger and bigger or they they harder and harder to solve and what lifted and i showed was that if um np had small circuits then this hierarchy would collapse down to the second level in other words you wouldn't get any more mileage by complicating your expressions with three quantifiers or four quantifiers or any number i'm not sure what to make of that exactly well i think it would be evidence that and np doesn't have small circuits because something because something so bizarre would happen but again it's only evidence not proof well yeah it's not that's not even evidence because you're saying p is not equal to np because something bizarre has to happen i mean there that's uh that's proved by the lack of bizarreness in in our science but it seems like um it seems like just the very notion of p equals np would be bizarre so any way you arrive at there's no way you have to fight the dragon at some point yeah okay well anyway for whatever it's worth that's what we proved awesome so so that's a potential space of open interesting problems yeah let me ask you about the this other world that of machine learning of deep learning uh what's your thoughts on the history and the current progress of machine learning field that's often progressed sort of separately as a space of ideas and space of people than the theoretical computer science or just even computer science world yeah it's really um very different from the theoretical computer science world because yeah the results about it algorithmic performance tend to be empirical it's more akin to the world of sat solvers where we observe that for formulas and arising in practice see the solver does well so it it's of that type it's where we're moving into the empirical evaluation of algorithms now it's clear that there have been huge successes in um image processing robotics natural language processing a little less so but across the spectrum of of game playing is another one there have been great successes um and one of those effects is that it's not too hard to become a millionaire if you can get a reputation in machine learning and there'll be all kinds of companies that will be willing to offer you the moon because they they think that if they have ai at their disposal then they can solve all kinds of problems but there are limitations one is that the solutions that you get by from to supervised learning problems uh through uh convolutional neural networks uh seem to perform amazingly well even for inputs that are outside the training set um but we don't have any theoretical understanding of why that's true secondly the solutions the the networks that you get uh are very hard to understand and so very little insight comes out so yeah yeah they may seem to work on your training set and you may be able to discover whether your photos occur in a different sample of inputs or not um but we don't really know what's going on we don't know the the features that distinguish the photographs or the objects are are um not easy to characterize well it's interesting because you mentioned coming up with a small circuit yeah to solve a particular size problem yeah it seems that neural networks are kind of small circuits in a way yeah uh but they're not programs sort of like the the things you've designed are algorithms programs right algorithms neural networks aren't able to develop algorithms to solve a problem is it well they are more of a function they are algorithms it's just that they're uh but sort of uh well yeah it's a it could be a semantic question but there's not a algorithmic style manipulation of the input perhaps you could argue there is yeah well it feels a lot more like a function of the input it's a yeah it's a function it's a computable function it's um once you have the network you can simulate it on a given input and figure out the output but what you you know if you're if you're trying to recognize images then you don't know what features of the image are really being uh uh determinant of of what the circuit is doing the circuit is sort of a very intricate and you know it's not clear that the the you know the the simple characteristics that you're looking for the the edges of the objects or whatever they may be they're not emerging from the structure of the circuit well it's not clear to us humans but it's clear to the circuit yeah well right i mean uh it's not clear to sort of the um the elephant how the human brain works but it's clear to us humans we can explain to each other our reasoning and that's why the cognitive science the psychology field exists maybe maybe the whole thing of being explainable to humans is a little bit overrated well maybe yeah i guess i you know you could say the same thing about our brain that when we perform acts of cognition we have no idea how we do it really we do though i mean we for at least for the visual system the auditory system and so on we do get some understanding of the principles that they operate under but uh for many deeper cognitive tasks we don't have that that's right so let me ask yeah you've also been doing work on bioinformatics does it amaze you that the fundamental building blocks so if we take a step back and look at us humans the building blocks used by evolution to build us intelligent human beings is all contained there in our dna it's amazing and and what's really amazing is that we have are beginning to learn how to edit dna which which is very very very fascinating this this ability to take a sequence find it in the genome and do something to it i mean that's really taking our biological systems towards the worlds of algorithm of algorithms yeah but it raises a lot of questions um you have to distinguish between doing it on an individual or doing it on somebody's germ line which means that all of the descendants will be affected so that's like an ethical yeah so it raises very severe ethical questions and um and even doing it on individuals um is uh so there's a lot of hubris involved that you can assume that knocking out a particular gene is going to be beneficial because you don't know what the side effects are going to be so we have this wonderful new world of gene editing uh which is you know very very impressive and it it could be used in agriculture it could be used in medicine in various ways um but very serious ethical problems arise what are to you the most interesting places where algorithms sort of the ethical side is an exceptionally challenging thing that i think we're going to have to tackle with all of uh genetic engineering but on the algorithmic side there's a lot of benefit that's possible so is there uh areas where you see exciting possibilities for algorithms to help model optimize study biological systems yeah i mean we we can certainly analyze genomic data to figure out which genes are operative in the cell and under what conditions and which proteins affect one another uh which prote which proteins physically interact um we can sequence proteins and modify them um is there some aspect of that that's a computer science problem or is that still fundamentally a biology problem well it's a big data it's a statistical big data problem for sure so you know the biological data sets are increasing our ability to study our ancestry by to study the tendencies towards disease to personalize treatment according to what's in our genomes and what tendencies for disease we have to be able to predict what troubles might come upon us in the future and anticipate them to to understand whether you um for a woman whether her proclivity for um breast cancer is so strong enough that she would want to take action to avoid it you dedicate your 1985 touring award lecture to the memory of your father what's your fondest memory of your dad seeing him standing in front of a class at the blackboard drawing perfect circles by hand and showing his his ability to attract the interest of the motley collection of eighth grade students that he was teaching when when did you get a chance to see him draw the perfect circles on rare occasions he i would get a chance to sneak into his classroom and observe observation and i think he was at his best in the classroom i think he really came to life and had fun um not only teaching but but you know engaging in chit chat with the students and you know ingratiating himself with the students and what i inherited from that is the great desire to be a teacher i retired recently and a lot of my former students came students who with whom i had done research or who had read my papers or who had been in my classes and when they talked about about me they talked not about my 1979 paper or my 1992 paper but about what they what came away in my classes and not just the details but just the approach and the the manner of teaching and so i sort of take pride in the at least in my early years as a faculty member at brickley i was exemplary in preparing my lectures and i always came in prepared to the teeth and able therefore to deviate according to what happened in the class and to really really provide a model for the students so is there advice you could give out for others on how to be a good teacher so preparation is one thing you've mentioned being exceptionally well prepared but there are other things pieces of advice that you can impart well the top three would be preparation preparation and preparation why is preparation so important i guess uh is uh it's because it gives you the ease to deal with any situation that comes up in the in the classroom and uh you know if you're if you discover that you're not getting through one way you can do it another way if the students have questions you can handle the questions ultimately you're also feeling the the the crowd the students of what they're struggling with what they're picking up just looking at them through the questions but even just through their eyes yeah and because of the preparation you can uh you can dance you can dance you can you can say it another way or give another angle are there in particular ideas and algorithms that computer science do you find were big aha moments for students were they for some reason once they got it it clicked for them and they fell in love with computer science or is it individual is it different for everybody it's different from everybody you have to work differently with students some some of them just don't don't need much influence you you know they they're just running with what they're doing and they just need an ear and now and then others need a little prodding others need to be persuaded to collaborate among themselves rather than working alone [Music] they have their personal ups and downs so you have to have to deal with each student as a human being and bring out the best humans are complicated yeah perhaps a silly question if you could relive a moment in your life outside of family because it made you truly happy or perhaps because it changed the direction of your life in a profound way what moment would you pick i was kind of a lazy student as an undergraduate and even in my first year in graduate school and i think it was when i started doing research i had a couple of summer jobs where i was able to contribute and i had an idea and then there was one particular course on mathematical methods in operations research where i just gobbled up the material and i scored 20 points higher than anybody else in the class then came to the attention of the faculty and it made me realize that i had some ability some ability that was going somewhere uh you realize you're pretty good at this thing i don't think there's a better way to end it richard was a huge honor thank you for decades of incredible work thank you for talking thank you it's been a great pleasure and uh your superb interviewer i'll stop it thanks for listening to this conversation with richard carp and thank you to our sponsors eight sleep and cash app please consider supporting this podcast by going to eightsleep.com lex to check out their awesome mattress and downloading cache app and using code lex podcast click the links buy the stuff even just visiting the site but also considering the purchase helps them know that this podcast is worth supporting in the future it really is the best way to support this journey i'm on if you enjoy this thing subscribe on youtube review it with five stars nappa podcast support it on patreon or connect with me on twitter at lex friedman if you can figure out how to spell that and now let me leave you with some words from isaac asimov i do not fear computers i fear lack of them thank you for listening and hope to see you next time you