Stephen Cook is a pioneering mathematician and computer scientist. Back when computers were still made of vacuum tubes Cook started thinking about the complexity of computer algorithms and came up with the concept of NP complete problems. Last year we had the pleasure of meeting Cook at the Heidelberg Laureate Forum and (along with other journalists) asked him questions about his work, computer science and artificial intelligence. To find out what NP complete problems are, read What's your problem?. Otherwise, see the very brief reminder in the box below.

You can also watch a video of the interview.

Why did you become interested in theoretical computer science, rather than any other area of maths?

Cook: We're talking about a long time ago now. When I went to graduate school in 1961 computers were pretty young: they were vacuum tubes and thousands of other [components]. My advisor [as a graduate student], Hao Wang, who was a logician, also had an interest in computers. He worked for IBM for a while. That influence [made me realise] that there are interesting questions in complexity theory.

Please tell us about your current work on complexity classes, such as P and NP.

Cook: We have a whole range of difficulties of complexity classes. Polynomial time [P] is supposed to mean feasible: you can [solve problems in P] in a reasonable amount of time. But we have smaller classes where we are looking at the amount of memory needed in order to compute. The small class there is logarithmic space, in which the number of memory bits [needed] is only a multiple of the logarithm of the size of the input. Logarithmic space is supposedly a small part of [the P class]. But we complexity theorists are very bad at separating complexity classes. It's not just separating P and NP. Logarithmic space is supposedly a very small subset of P. Everything in logarithmic space can be done in polynomial time, but we cannot prove that [logarithmic space and P] are different. And it's much worse than that: we can't even separate logarithmic space from NP.

Will we need a completely new theoretical approach to separate the complexity classes and to solve the P versus NP problem?

Cook: We certainly need some new ideas, that's for sure. I'm not sure what you mean by "approaches". Our approach is to think hard about the problem.

But is the barrier that you hit when you try to prove that logarithmic space is smaller than P similar to the barrier that you hit when you try to prove that P is smaller than NP?

Cook: The problems are definitely related. But the sad story is that we just don't know how to proceed to [solve them]. Obviously a huge amount of effort has been put into that. I've been particularly thinking about separating logarithmic space from P because we have simple examples of problems that are in P, and there seems to be no way of doing them in logarithmic time [which suggests that logarithmic space and P really are different]. But there seems to be no way to prove it.

Stephen Cook at a press conference at the Heidelberg Laureate Forum 2017. Picture/Credit: Christian Flemming/HLF.

What does the NP hardness of problems like the travelling salesman problem mean in practice, for people who do really need to solve such problems in real life?

Cook: What's NP hard of course is finding the exact best order of cities. That's very hard, but there are algorithms to approximate the best route. You can argue 'why do we need to have the exact [solution]?'. That's true. But there are certainly questions where [an approximation isn't good enough]. If you're in cryptography and you want to show that you can't break the RSA encryption scheme — [to break the scheme] it doesn't help if you can approximate the [solution]. So there are reasons for showing that problems are impossible.

Will quantum computers help with solving NP complete problems?

Quantum computing in principle seems to be very powerful. For example, quantum computers in principle can factor large numbers into their prime factorisations. My understanding, though, is that in practice quantum computer are well behind what they are supposed to be able to do. Actually making them work seems to be a huge problem.

They are able to solve problems that are in NP that we don't know how to solve in polynomial time. The factoring problem is the best example: when you have a product of 2000-digit prime numbers it's easy to multiply them, but when you are given the product finding the prime factors [is something] we don't know how to do [in polynomial time]. The RSA encryption scheme depends on that assumption. In principle quantum computers are supposed to be able to do that, my understanding though is that in practice they can't — yet.

How did you come up with the concept of NP complete problems?

Cook: My advisor, Hao Wang at Harvard, was interested in logic and recursion theory. What led me to this idea was the theory of computable functions, which has so-called recursively enumerable sets. You had recursively enumerable complete sets and they were all equivalent to the hardest recursively enumerable set. Of course the difference was that these sets were not decidable: there was no algorithm that could solve them at all. But that was the analogy. Of course NP complete sets are computable, though not feasibly computable. Presumably, we guess, it takes an exponential amount of time to solve the problem. But the analogy was there. That's where I got the idea.

How far away are we from creating an artificial intelligence that can trick us into thinking that it's human (pass the so-called Turing test)?

A monarch butterfly. Image: Kenneth Dwain Harrelson, Creative Commons.

Cook: It's hard to know. That's not my field; I have lots of colleagues thinking about that. I guess the worry is that the AI robots can start competing with us in more and more areas. So what are we to do then? I don't know the answer to that.

Self-driving cars [for example] seem to be developing pretty fast, there seems to be some sense that they are going to exist, they will replace drivers and they are ultimately going to be safe. That's relatively easy. But replacing mathematical thinking, and other thinking, is a different question, that's much harder to say. Ultimately I suppose there's no reason to think that machines can't do what people can do. There's no barrier there that I can think of, it's just a question of time.

So do our minds work just like computers do?

Cook: I think our brains are computers. There are billions of neurons and they are extremely complicated computers. That's why ultimately I assume that we can build computers that can do what we do. I don't see any barrier there. I know there exist scientists who think there is a barrier, but I can't see it. That's the way it is. What to do about it is a different question. What is our role? What is the role of humans is a different question. Right now of course our minds seem to be more sophisticated than robots and AI. But that's just the beginning of what's going to happen.

As I mentioned before, and as everyone knows, we have extremely complex and sophisticated brains. [But an interesting point is that] even insects can do amazing things. Look at the monarch butterflies that manage to find a way from Toronto to Texas or Mexico and all know where to go. At this point we can't build machines that are as small as butterflies and can do anything like that. So in a sense there is long way to go. And of course butterflies have relatively small brains.

Also, I watch the squirrels in the back yard climbing the trees and jumping here and here and there. That's not thinking, that's motor control. They have huge motor control: they can keep their balance and they estimate where to go, and this and that. We can't do that. I guess there's a long way to go. I just can't see why ultimately it can't be done.