Skip to main content
Loading Explore guides…
Computational Complexity · Acedra
Home
Explore
Other
Computational Complexity
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
164 segments
Copy
Hide video
0:00
[SAM BUSS] --drifting in. But let's go ahead and get started. First of all, some practical things. Uh, so the first talk's gonna be by Dick Karp, and I'll give a brief in-- introduction in a minute, but I'm gonna say some practical things first. So first of all if you haven't attended the meetings before the talks are gonna last about 35 or 40 minutes, and then there's about 15 minutes for discussion. But the discussion can also be interspersed with
0:24
the talks if you wanna ask questions in the middle. If you wanna ask questions please type into the chat windows and we either have a Q&A window if you're an attendee or you have a chat window if you're a panelist. If you do type into the chat window as a panelist, here, you're encouraged to pick the option to send your chat to all panelists and attendees. That's not the default. The default is to just all panelists so that everyone will have the benefit to see your comments.
0:54
And I'll be watching the chat windows and possibly will interrupt the speaker with questions depending on how the talk is going and how I, how I'm feeling at that moment.
1:07
So, let's see. Um, Dick is not gonna use any overhead tran-- transparency, so you might wanna pick the speaker view on Zoom. It's up in the upper right-hand corner of your window. And otherwise, we're about ready to get started. Uh, our first speaker is Richard Karp. He's a great-- We have two very distinguished speakers, of course. And I was just gonna-- So I'm not gonna say too much here. Um uh, he's, he's been at Berkeley since approximately, I think, 1968, with a short break in the middle.
1:39
Uh, he was the founding director for the Simons In-- In-- Institute as well. He's won new-- numerous awards and prizes, which I'm not gonna list. Uh, but I wanted to mention his 1972 land, land, landmark paper on reducibility among combinatorial problems which along with Steve Cook's paper the prior year, was one of the ones that really set the foundations for the modern study of the theory of computer science, with the PNP questions and so on. And so I believe he's gonna be talking about things
2:12
around that topic today. The title of his talk is The Dawn of Computational Complexity. And Dick go ahead.
2:21
Thank you. [RICHARD KARP] Okay. Hello everybody. I hope you can hear me. It's good to see you, those that I can see.
2:29
Let's go back to 1971. In 1971 Steve Cook proved that if a set is in P, then P is equal to NP.
2:45
This audience is probably entirely familiar with all of the terminology in that statement. But just for the record, let's go through it. P is, of course, the-- We're dealing, first of all, with decision problems, where the input is a string of symbols over a finite alphabet representing some mathematical structure.
3:07
And the task of the algorithm is to either accept or reject any particular input.
3:18
P is the class of determinist problem solvable in polynomial time by deterministic algorithms.
3:27
Np is the class solvable in polynomial time by non-deterministic algorithms. A more illuminating description of NP is to say that in NP the problem is to test whether a particular string called a witness actually witnesses the reception of the input.
4:09
So class NP consists of a very wide class of problems, including virtually all of the typical optimization problems that arise in applications. And it seems to be a much broader than P, where the requirement is not just to recognize some input, but to accept make a decision about input strings.
4:56
So intuitively, we are inclined to believe that P is unequal to NP because it appears that solving a typical problem in NP entails an exponential search.
5:16
But this is unproven, and it is a central problem in complexity theory.
5:24
Later in the talk, we'll
5:27
talk about other problems that can play the same role as satisfiability.
5:34
Namely so we'll say that the problem X is NP complete if we can make the inference that if X is in P, then P is equal to NP. And those NP complete problems are considered to be the hardest problems in the class NP.
5:56
Uh, so I'll return to Cook's theorem and its consequences a little bit later in the talk. But right now, what I want to do--Um, rather than a talk that looks toward the future, as you might expect in such a conference I'll be looking to the past and trying to give you a view of the experiences I had starting in 1959 after, just after my PhD at Harvard going through the IBM Research Center, and the developments that I witnessed between 1959 and 1971, the date of Cook's paper.
6:37
So in 1959 there was no complexity theory. There was one somewhat sketchy think piece by Michael Rabin, but really not much else.
6:49
But there was a certain amount of work on combinatorial algorithms. Uh, I-- in particular George Dantzig had created the simplex algorithm for solving linear programming, the problem of minimizing or maximizing your linear function and variables subject to linear inequality constraints.
7:15
This algorithm was immensely valuable and highly reliable in practice, but it was known that it was not a polynomial time algorithm. In fact, there were instances known that would cause it to run for exponential time. So the pedigree of the simplex algorithm was not entirely clear despite its actual effectiveness in practice. Um, another early result that was influential was the work of Rabin and Scott on finite automata where they introduced the notion of a non-deterministic algorithm,
7:53
a non-deterministic finite automaton in that case. And that concept of non-determinism has turned out to be essential in complexity theory.
8:10
There were also a number of algorithmic developments. I'll mention a few related to graphs in particular. Uh, as early as 1926, Boruvka had given a fast algorithm for m-- minimum spanning tree. There were algorithms for computing shortest paths and graphs flows and cuts in networks computing the testing whether the graph was strongly connected, et cetera.
8:46
People at the time were not very rigorous about estimating the running time of an algorithm. They were sort of more intuitive as to whether the algorithms seemed good to them. And so uh, for example Ford and Fulkerson, who created the Max Flow Min-Cut Theorem never bothered to check whether the max flow algorithm that they gave ran in polynomial time. And in fact, as stated, it did not, although it could be fixed to run in polynomial time as Jack Edmonds And I later showed.
9:23
So there was a certain amount of looseness about
9:28
estimating the time. And in particular, there wasn't much sophistication about data structures. So that came along later where very inventive data structures were created to whittle down the running time of some of these algorithms to close to linear time. Um, Bob Tarjan was the leading architect of that kind of data structure work.
9:57
So um--
10:03
There were certain problems that were cons-- uh, they were viewed as as hard, although this was, this was based on just the in-- inability to solve them rapidly, rather than any theoretical considerations. And so, in particular George Dantzig, the creator of the simplex algorithm uh, felt that the integer programming problem was a good candidate for being the central or quintessential problem to which others to, to which many applications could be mapped.
10:45
So you recall that linear programming problem is to
10:51
find the highest point on a polytope in n-dimensional space.
10:58
And the simplex method attacks this problem by walking on an increasing path along edges of the polytope until it can't improve anymore.
11:10
The integer programming problem is a related one.
11:15
It's the linear programming problem plus the requirement that the variables be integers.
11:24
And that makes the problem much tougher. But there is a, an approach called the cutting plane approach which seems to be quite powerful in solving integer programming problems. The idea is the following. The as we said, if we ignore the integrality constraints, then we get the linear programming problem of minimizing linear function over a polytope with the requirement that the variables be integers.
12:01
We restrict the feasible region not to that polytope, but to the vertices of the convex hull of the integer solutions. So it's a polytope So you're, we're working with a polytope
12:17
inside the one arising in the fractional problem. And so the idea of a cutting plane approach is to solve the fractional problem and then devise a linear inequality which is satisfied by all of the integer solutions to the problem, and add that inequality, thereby cutting off part of the polytope. And so the cutting plane method proceeds by slicing away at the linear programming polytope until a contained polytope is obtained whose highest point is integral.
13:05
And this technique does work well in many cases, but without real guarantees. My colleague, Dan Gusfield, has said, "Always try integer programming, it might work."
13:19
Um so
13:22
a notable result around 1960 was due to Ralph Gomory who showed that a particular variance of the cutting plane method
13:34
actually terminated with an optimal solution, al-- although he could not give any bounds on the running time of the algorithm. The number of iterations of cutting that would be required. Um, further evidence for the cutting plane approach was provided by Dantzig, Fulkerson, and Johnson, who solved a pro-- uh, a traveling salesman problem over through where the cities are the state capitals of the continental US states plus the s-- uh, state of s-- city of Washington DC.
14:15
So, it was a 49-city problem which they solved by the cutting plane method.
14:25
Solved efficiently by the cutting plane method.
14:29
Uh, this approach was taken up by taken up further by Applegate, Cook Kvatal, and Bixby, who tried to apply it to the traveling salesman problem.
14:45
So the idea there is to start with a linear programming relaxation of the traveling salesman problem, and then to hack away at it with cutting planes until an optimal integer solution is obtained.
15:05
The traveling salesman problem can be formulated as finding a minimum total cost set of edges of a graph with the vertices are the cities subject to the requirement that two edges are chosen each, incident with each vertex. And for each partition, non-empty partition of the set of cities in two parts at least two edges must run between the two parts. So the linear programming problem is which is being relaxed, is to imitate those constraints, but with now fractional weights on the edges.
15:56
So that, for example, instead of having two edges out of an edge, you have many edges with fractional participations summing to, to-um, and amazing results were obtained in using the cutting plane method starting with that linear programming relaxation and hacking away at the polytope.
16:21
And problems with as many as 80,000 cities were solved although, with a, an extravagant computing requirement.
16:35
Meanwhile still in the early to mid '60s we saw the beginnings of complexity theory. There was a fascinating formulation of complexity theory in an axiomatic way by Emanuel Blum, where instead of measuring the computational resource as time or space, it was any resource satisfying a, a certain natural constraint. Um, and Blum working in, in that axiomatic approach was able to prove amazing theorems such as the fact that there exist algorithms which use time, or space,
17:19
or any related resource so much that every, uh-- there's a problem such that every algorithm for the problem can be improved exponentially. No matter how many times you integrate the improvement, you keep getting exponential improvement. And there were other fascinating results, but the one that was-- the, the approach that was uh, perhaps more lasting in its effects was started by Hartmanis and Stearns, which studied the resources of time and space on the
17:55
Turing machine and defined complexity classes accordingly, and proved hierarchy theorems showing that a little bit of increase in the available time, or in the available space allows a larger set of problems to be solved. And they actually looked at other things, like s-- simulating a two-tape more Turing machine on a single tape machine, and other simulation results. So this work was very influential in getting complexity theory off to its start.
18:34
But a more revolutionary approach was to focus on the boundary between polynomial-time and non-polynomial time. And this approach was uh, advocated by Alan Cobham, who wrote a paper where he described, defined the class that we now call P. Explained why it was important, that it was a reasonable theoretical formulation of the notion of efficient solvability to say when a problem is in that class.
19:17
He even hinted at the definition of NP. And this rather prescient result was hardly noted by the community.
19:33
I never heard about it at the time. And in fact, I never met Cobham, although we worked in the same large industrial laboratory. But he could be credited with the first one to publicly reference the importance of the class P.
19:51
Sometime in the mid '60s
19:55
I began collaborating with Jack Edmonds. We did some work on network flow problems, on matching problems, on the problem of pairing up boys and girls so as to minimize the total benefit of all of the pairings, the so-called assignment problem. And we improved the time bounds for some of those problems. As I mentioned, we gave a polynomial-time bound for variant of max flow. But more important than the research we did together from my point of view at least, was the opportunity to visit
20:40
Jack at his workplace at the National Bureau of Standards, and ha-- allow him to give me a discourse on the wonderful results he was obtaining. Polynomial-time algorithms for the non-bipartite matching problem for matroid intersection, for other problems, other graph theoretic problems where he showed that these problems were in P.
21:21
But also noted in passing that they were in NP intersect coNP. And it led him to the conjecture, not yet disproven, that P is equal to NP intersect coNP.
21:37
Um, but I, I was, again, strongly influenced by Jack's approach with the emphasis on polynomial-time algorithms. And his ideas were at the centerpiece of most of the graduate courses that I taught for a number of years on combinatorial optimization.
22:03
In one of those courses Silvio Micali and Vijay Vasarani were, uh-- first year graduate students that were taking the course. Uh, and I told them in the course about the result I obtained with John Hopcroft about maximum matchings in bipartite graphs showing that you can compute a maximum matching in time. Square root of the number of vertices times the square of the number of edge square root of the number of vertices times the number of edges into the five halves in other words.
22:43
And the challenge that I gave them was to show that the same time bound could be obtained for non-bipartite matching, which is a much more difficult problem.
22:54
And they got excited about this problem and started working on it avidly, totally forgetting about all of the requirements of the course that they were sitting in. And as the end of the semester approached, I had a dilemma because they hadn't done any of the required work for the course, but they seemed to be getting close to solving this problem. And so I decided to give them the highest pass the lowest passing grade that would still not get them kicked out of graduate school.
23:27
A little later, I apologized to both of them for my rough treatment of them, but they didn't seem to really care.
23:42
So getting back to uh, Cook's work
23:46
I, I saw his 1971 paper and I had had enough experience with combinatorial optimization and w-- combinatorial explosions that seem to occur in many of these problems that I was, I felt certain that there were many problems that had the same, that, that had more or less the same status as the satisfiability problem that they were also in NP and um, I was convinced that they were at least as hard as satisfiability. And so I began to try to prove that these problems were what
24:39
we now call NP-complete. And the approach to solving them was based on polynomial time reductions, which are modeled after the mapping reductions that have been used in computability theory to compare the difficulty of different the computability to solve the to prove the certain problems are undecidable.
25:06
And the setup for the polynomial time reducibility is the following, that if we have two decision problems A and B, each having input strings which are either accepted or rejected, we say that problem A is polynomial time reducible to problem B if there exists a polynomial time algorithm which maps strings in A to strings in B such that accepted strings in A map to accepted strings in B and rejected strings in A map to rejected strings in B.
25:53
And it then follows that if problem B is in the class P, then so is problem A.
26:05
And so the strategy was to start with the satisfiability problem and give reductions of this kind gradually showing more and more problems that the satisfiability problem is reducible to. And sinch, and, and since we also know from Cook that every one of those, that's, that there's a reduction from each of those to SAT, we know that all of these problems have the same status. They're either in P or in NP or not in either all in P or either or and or all not in P.
26:42
And these are called the NP-complete problems which are equivalent in this, in the sense of, in, with respect to membership in P, although they're not equivalent in some other respects.
26:57
And so the task was to gradually create reductions from satisfiability to other problems, bringing them into the NP-completeness circle.
27:13
The reductions were not too hard to find. The task was simplified by the observation that polynomial time reducibility is a transitive relation. So if you've already proven that satisfiability is reducible to problem X and if X is reducible to Y, then satisfiability is reducible to Y. So with the help of that observation it was possible to demonstrate that a large number of problems, 21 in my original paper, were in were NP-complete. And by now using reductions, thousands of problems have
27:58
been shown to be NP-complete.
28:03
In my reductions, I tended to not give the sharpest possible results. So for example, I proved that graph coloring is NP-complete. Um, but, uh-- uh,
28:19
Gary Johnson and Stockmyer proved the much sharper result that the three coloring problem for regular planar graphs of degree 4 is NP-complete. And similarly, with the Hamiltonian circuit problem
28:37
instead of just showing that the Hamiltonian circuit problem in general is NP-complete
28:43
Gary Johnson and Tarjan showed that it's, it's complete even for cubic three co-- uh, three connected planar graphs, so much more refined results were, were obtained. And thousands of results of that type were obtained. There was a flurry of them in the few years after 1972 but eventually it quieted down. And nowadays you can't really publish an NP-completeness result unless the reduction is particularly clever.
29:25
Meanwhile there were attempts to extend-- to go beyond the setting of P versus NP and to obtain complexity results for higher levels of complexity. Um, Meyer and Stockmyer
29:54
showed that if you ex-- if, if you extend the definition of regular expression to include the squaring operator then you get a problem which requires exponential space. And they also, the same duo looked at a decision problem in logic where they showed that the, for a problem of, for an instance of size 610 the number of computation steps would inevitably require, be larger than the number of protons in the known universe. So the techniques of reduction and for proving complexity
30:40
bounds were carried out beyond the level of the class NP.
30:53
So much has gone on since 1972, including extensive work on approximation algorithms for the combinatorial optimization versions of problems and also magnificent results about hardness of computation of approximation. But in closing, let me turn my attention back to the satisfiability problem and make a couple of remarks.
31:48
So now talking about the problem of deciding whether a formula in normal form conjunctive normal form is satisfiable. The prevalent approaches seem to be to use either resolution or the CDCL approach in which one starts selecting literals to, to be true and follow up their implications in terms of creation of unit clauses, which also have to be satisfied until a clash is obtained. And then going back from the discovery of that clash to learn a new clause to add to the problem.
33:02
These approaches using resolution and using conflicts resolution seem to me to be rather primitive. And it's to me amazing that they approach together with additional heuristics to solve problems with millions of variables. But this seems to be the case, and I, I'm entirely puzzled by it.
33:33
Um, I'm also puzzled by other algorithmic developments that seem to be outside the scope of complexity theory as it's currently practiced. So for example there are results on programs that play chess better than any human. On AI approaches to of labeling algorithms according to, labeling images, recognizing images, classifying images, where the results seem to be very good, but there's no well-defined metric from the point of view of complexity theory to allow us to prove things
34:26
about how hard these problems reason really are. So I think I'll stop at this point, and I'd be happy to take questions.
34:40
[SAM BUSS] All right. Thank you so much for rather inspiring talk, I must say. It was very, very good, and I love also your final comments. So, people can't clap, so I'll clap on their behalf, and then we'll have some questions for you and so on as well. Good. All right. So again feel free to drop questions in the chat windows, and I'll, I'll, I'll take them probably in the order they're stated, more or less. We already have one question from Karam Sakala.
35:06
Uh, Karam, do you wanna, do you wanna state it or shall I read it for you?
35:12
[KAREM A SAKALLAH] You can go ahead and read it. [SAM BUSS] Okay. All right. So-- You [RICHARD KARP] Read it to me. [SAM BUSS] So Karam asks, "The relation between linear programming, LP, and integer linear programming, ILP, is strikingly similar to counter-example-guided restriction refinement in model checking.
35:32
Linear programming is a sound abstraction of ILP, and cutting planes serves as refinements that increase the precision of abstraction by eliminating infeasible solutions. Is this an obvious connection, and has it been noted before?"
35:50
[KAREM A SAKALLAH] Um, I don't think I'm prepared to answer that. [SAM BUSS] Okay. Okay.
35:56
Let me see
35:59
if I can phrase that. Yeah okay. Well yeah I mean, I, I think Karam's just remarking on the fact that at the very beginning you talked about the-- or not the-- close to the beginning, you talked at length about integer pro-- pro-- programming and the connections to SAT and so on. So I'm not sure I can answer his question either. Just thought I'd raise it. Okay. Yeah. Okay. So while people are, while people formulate some questions, if I can, maybe I'll ask one of my
36:28
own while waiting for people to give some questions here. I was just, was wondering, while you were speaking, you were talking about Steve Cook's 1971 paper. And I, I believe you overlapped in time, time-wise with, with at Berkeley with Steve. Is that correct? And I know S-- Steve did seminars on this, on these topics at Berkeley. Is there, was there any interaction or feedback back in those days between the two lines of study? [RICHARD KARP] No.
36:54
I, I knew Steve very well while he was at Berkeley and was very saddened by the fact that he moved to the University of Toronto.
37:04
But I became aware of this, I knew of some of his earlier work from his thesis at Harvard, for example. But I only learned about this work by reading his 1971 paper.
37:17
So we actually never discussed those issues until I had already absorbed his paper. [SAM BUSS] Right.
37:30
So it's, Yeah. So it's intriguing. You ended with a comment that resolution and CDCL are strikingly successful and were lacking complexity results for Y. This is the case. Do you have any thoughts about what might be the right approach to this and so on?
37:48
[RICHARD KARP] Well there have been some complexity results. Um there's a paper by uh, Beam Mike Sacks
38:02
uh, another co-author, and with me as a courteous courtesy co-author because I made one small satisf-- observation about 2-SAT
38:12
And somehow they stuck my name on the paper. Um
38:19
where they explore the threshold for random case SAT and how many cla-- how many random clauses you need before a, a Boolean expression becomes un-- uh, unsatisfiable.
38:36
And they derived some bounds on that. And of course, there is work by several people on proof complexity for the pigeonhole principle and other particular formulations particular instances where there proved to be exponential for ordinary resolution.
38:59
I haven't seen, I'm not an expert on this, but I haven't seen results on complexity results for CDCL, just the observation that it seems to work very well on the problems that arise naturally in applications.
39:20
[SAM BUSS] Okay.
39:22
Good.
39:24
Let's see. Um, Albert Ots-- uh, Albert Otsirios is asking a question. He asks, "Would you comment on the role of randomness in designing algorithms in the early times of P versus NP?"
39:40
[RICHARD KARP] Yeah. Yeah, after my NP-completeness paper, I was rewarded for the work by being made an administrator.
39:51
And so I, I served as, in an administrative position at Berkeley for a while. And suspended my work on NP-completeness, but I began to take up another line of work studying the complexity of algorithms on random instances of graph theoretic problems.
40:15
And so um, I looked at things like uh, constructing maximum matchings or uh, finding Hamiltonian circuits in random graphs and what density is required. And again, there are critical densities and one can derive algorithms that are fast up to a certain density. So I worked on a number of problems like this. I worked on the traveling salesman problem where the cities are randomly distributed over a region of the plane. And there were some very nice gratifying results.
41:06
But I decided that the assumption of Erdős-Rényi random graphs, for example, or uniform distributions over the plane were just not realistic. They didn't capture the nature of real applications.
41:25
And so I decided after a while that while it was fun doing this kind of probabilistic analysis, that it wasn't probably going to change the world because of the artificiality of the probabilistic assumptions.
41:44
[SAM BUSS] Okay.
41:47
Okay. Yeah. So I'm not speaking, maybe speaking on Albert's behalf o-- out of turn, but I was just saying he, he might have also been meaning the use of random algorithms for solving problems with high probability. Uh-- Oh, [RICHARD KARP] Yeah. Sure. Yeah. Well-- [SAM BUSS] I'm not sure what he meant. Yeah. [RICHARD KARP] Mm. Yeah. Of course I mentioned in my NP-completeness paper that there were three problem areas where I wasn't able-- would have liked to settle the complexity question
42:21
and couldn't do it.
42:25
One was primality, the second one was graph isomorphism, and the third one was linear programming.
42:34
And in the case of primality of course, there was a major breakthroughs such as the Miller-Rabin randomized algorithm. And that was a very striking result.
42:59
It left open the question of whether primality was in P and that was settled several years later by AKS, the trio from India.
43:11
But for a while the only polynomial time algorithm known was randomized rather than deterministic.
43:23
Mm-hmm. And
43:26
there's also the question of quantum algorithms where we don't know that P and a quantum machine is the same as, as P and a Turing machine with another direction to explore. [SAM BUSS] Right. Mm-hmm.
43:41
Okay. Good. Let's see. There's several questions here in the chat window. So
43:51
well, let's see. Let me take one at a time. So, so Thomas Kochman asks "When in the '60s or '70s did you intuitively start expecting Hawkins intractability of resolution, which came in the '80s?" So I guess this sort of implies you did start expecting this. So you, you-- so the point was Ar-- Armin Hawkins proved that re-- re-- resolution re-- requires exponentially long proofs for things like the pigeonhole principle. And the question is, did you have an in--
44:20
did you anticipate this in terms of conjecturing it or expecting it or,
44:26
[RICHARD KARP] No, I don't think I had an opinion about it. I followed the work And I knew that there were attempts to prove the pigeonhole principle required exponential time in various settings. But I didn't participate strongly in-- I didn't have any intuitive conjectures about that.
44:50
[SAM BUSS] Okay. Okay. Uh, and Karen Sokal has another question. So let me just read it to you. "the problem I see with current complexity theory is that it generally ignores problem structure, however that is defined. Is there a reason why this is so? Is it just hard to characterize problem structure?"
45:13
I think he's coming back to your question. You can, he can correct me if I'm wrong, of you were saying how, again, re-- resolution in CDCL work unexpectedly well. [RICHARD KARP] Yeah. [SAM BUSS] And so this seems to be due to some structure in the inputs, right? So he's asking about this, yeah.
45:29
[RICHARD KARP] Yeah. Um there's a forthcoming book
45:36
which which deals with um, edited by a colleague at Columbia whose name uh, T-- uh Tim,
45:50
uh-What's Tim's last name from co--
45:54
--Anyway Tim. Tim [KAREM A SAKALLAH] Roughgarden. [SAM BUSS] Roughgarden. [RICHARD KARP] Yeah, Tim Roughgarden. Uh, Tim has edited a book dealing with this issue of the behavior of algorithms for particular classes of inputs
46:14
and other ways of assessing the value of an algorithm rather than its worst case performance. So one can look at algorithms operating on graphs with small tree width or clustering problems with the side assumption that all of the near-optimal solutions are very similar to one another and prove that for the, for those kinds of restrictions on the problem space, the algorithms perform much better than in the worst case.
47:01
There are also results showing that while the simplex method has those failings that it, there are contrived examples where it runs in exponential time one can show that if you-- if-- even for those examples, if you randomly alter the data infinitesimally, you get rid of the bad examples. So the right examples are really a very low measure in the space of all problem instances. So there this forthcoming book edited by Tim Roughgarden will cover a large number of the investigations of that kind.
47:51
I think it's a very useful line of research.
47:57
[SAM BUSS] Okay, good.
48:01
Let's see. Another question. Chiar-- Chiar McCrich asks the following question.
48:08
"in your NSF report from 1996, on the theory of computing goals and directions you said the theory community had to recognize the importance of algorithm engineering.
48:20
Do you think they have done so?"
48:25
[RICHARD KARP] Yeah. I mean, there are many lines of investigation, I think, which take into account the details of the platforms in whi-- on which algorithms are taking place, whether they take place in the cloud. Um um--
48:52
They're-- They're-- I mean, there are min-- uh lots of details about making algorithms really work well and measuring them properly. Um the um--
49:05
There was also I'm not sure if I'm answering direct-- or exactly the question but there is a feeling that one should really focus on algorithms that are, at worst, quadratic in their running times, because we're getting so many data sets are so large now, that any algorithm whose imports --uh, consist of a large dataset really has to run low polynomial time rather than polynomial time in general.
49:38
There's a lot of work on sublinear algorithms, streaming algorithms. There's many different directions that may be suitable, depending on the
49:49
circumstances where the computation is happening.
49:54
In terms of algorithm engineering, in terms of writing code that works well I don't write code, so I can't comment on that.
50:07
[SAM BUSS] Okay. Good. Um, Ryan Williams has a question.
50:13
It's a bit long. I guess I can read it. So he says, "This question is a bit vague, but it is relevant. In complexity theory, running time is or was the most precious resource that is studied in tremendous detail compared to other resources an algorithm might consume. Do you think this was an inevitable development? Man-- Manuel Blum and I used to argue about this, and he suggested that complexity theory, quote, could have, quote, developed in other directions,
50:42
and running time just happened to be what people were interested in decades ago. I thought time was central to the entire idea of complexity theory."
50:55
[RICHARD KARP] I think time is central. It's natural. I suppose, there's, there should be some measures of the complexity of the algorithm just in terms of the conceptual difficulty of grasping it, or the difficulty of realizing it as a program. Um, I also love Manuel's axiomatic approach and the amazing theorems that come there for arbitrary complexity measures. But I would tend to side with Ryan and think that um,
51:40
time is probably the resource you'd think of most. Maybe there are resources related to communication when a problem is done in a distributed setting that should be considered, the number of bits that the different parties to the algorithm have to exchange.
52:01
[SAM BUSS] Mm-hmm. Good. All right. Let me see. One last question is maybe a easy one then. It was VJ Ganesh asked earlier, "Is there a resource on the history of complexity theory that you would recommend?"
52:17
[RICHARD KARP] On the history of complexity theory.
52:21
Um,
52:25
um--
52:32
No. There's a nice book about the PNP story that has been published.
52:43
Again, help me out with the name. It's um--
52:46
[KAREM A SAKALLAH] Lance Fortnow? [RICHARD KARP] Yeah. Yes. Okay. La-- Lance Fortnow. Yes. I, I've enjoyed reading that. There's a, that's a nice exposition for the public. But I think you're asking about a major technical overview. Of course, there are very good texts on complexity theory by various authors.
53:18
[SAM BUSS] Yeah. Let's see. I guess the name of the book is The Golden Ticket, is that correct? [RICHARD KARP] Golden Ticket, yeah. Yeah. [SAM BUSS] Yeah. Okay.
53:29
Great. Yeah, I would say a lot of things you talked about today are, aren't studied that actively, you know, like time, alternatives to time, complexity for instance now and things like that. Mm-hmm. But the field has as it should have moved on to new things, right?
53:49
But you know. [RICHARD KARP] Well, I would single out communication complexity as a thriving area. So does the number of bits that Alice and Bob have to exchange in order to, to make a decision.
54:05
That seems very well motivated.
54:10
[SAM BUSS] Good.
54:11
All right. Well, thank you again so much on behalf of everyone. I wish there was some way we could all applaud, but I'll do it for the group again. So that was a wonderful talk. I found it very inspiring, and it was great to hear all this. So, we're gonna take a four-minute break till the half hour So if you need to stretch your legs, whatever, and then our next speaker will start. Um and
54:40
V-- Vijay mentions, he's just Googling right now, he's found a book on Google called The History of Mathematical Logic by Dirk van Dollen and John Dawson and Ake Kanav-- Yeah. I'm on it. --and Aki Kanamori.
54:51
Okay. So we'll take a three-minute break now And we'll be right back. Okay.
54:58
Thank you again. That was a great talk.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat