Joel David Hamkins: evaluation

Transcript context

…The amount of fields and topics you’ve worked on is truly incredible. I have to ask about P versus NP. This is one of the big open problems in complexity theory. So for people who don’t know, it’s about the relation between computation time and problem complexity. Do you think it will ever be solved? And is there any chance the weird counterintuitive thing might be true, that P equals NP? Yeah, that’s an interesting question. Sometimes people ask about whether it could be independent, which I think is- …an interesting question for logicians. And of course, well, one has to say if you’re entertaining the idea of independence, you know, over which theory? Because every statement is going to be independent over an extremely weak theory. So that’s, you know, it doesn’t make sense to say it’s independent all by itself. You’re only independent relative to a theory, right? So the way I think about P-NP is that… I mean, of course it’s a theoretical question about the asymptotic behavior of these problems. I mean, for a problem to be in P means that there is a computable decision procedure that runs in time bounded by some polynomial. But the coefficients on that polynomial could be enormous, and the degree could be incredibly high. And so for small values of inputs, then it doesn’t make sense to talk about this polynomial time feasibility with respect to, say, the range of problem inputs that we will ever give it in our lifetime or in the span of human civilization or whatever. I mean, because it’s an asymptotic property, it’s really in the limit as the size of the inputs goes to infinity, that’s the only time that polynomial or NP becomes relevant. And so maybe it’s important to keep that in mind when… Sometimes you find kind of overblown remarks made about, you know, if P equals NP, then this will be incredibly important for human civilization because it means that we’ll have feasible algorithms for solving these incredibly important… …problems in NP. You know, that it would cause immense wealth for human societies and so on because we would be able to solve these otherwise intractable problems, and that would be the basis of new technology and industry and so forth. I mean, people make these kinds of remarks, but… Of course.…

Stored transcript either side of the excerpt. The highlighted words are the published quote; the surrounding text is unedited source, never generated.