Why are there complete problems, really?

This post aims to show a surprising connection between a well-known computer science concept (NP-complete problems) and the reasons for why computers have become so ubiquitous in the modern world. If you’ve never heard of NP-complete problems the “Why computers are special devices” section might still be of interest!

Context

Many people interested in computer science or software engineering will have heard of “NP-complete problems”.

These are often said to be the “hardest problems” in class NP. The class NP is a broader class of search problems where a solution, once found, can be efficiently verified as correct. Consider for example this problem: you’re given a social network and a number K and you need to figure out if there is a group of K people in this network that all know each other. That is an NP-complete problem.

The reason these problems are said to be the hardest in NP is because they have a remarkable property – it has been shown that if you found an efficient algorithm for any of them you could use it to construct efficient algorithms for all problems in NP. This is why they are called “complete“ - they capture every problem in the class while also themselves belonging to it.

It is also why recognising an algorithmic problem as NP-complete is usually taken as a sign that looking for an efficient algorithm to solve it is hopeless and one should instead be looking at heuristics or approximation algorithms.

Puzzle

But why do problems with this peculiar property exist? Their existence is counterintuitive because having the ability to answer questions about one kind of object is not usually associated with being able to answer questions about other kinds of objects. Why should the ability to answer questions about cliques in social networks confer the ability to also answer questions about … well, anything else really?

And the mystery doesn’t quite stop there. Computer scientists have defined many other complexity classes.

And looking through the list you can observe a recurring phenomenon. Many of these classes have complete problems as well. There aren’t just NP-complete problems - there are PSPACE-complete problems, #P-complete problems, EXP-complete problems and many others. Completeness is in no way an NP specific phenomenon.

Is there a unifying reason why all these different classes have complete problems?

To see that there is we must first look at a seemingly unrelated question – why did computers become so ubiquitous in the modern world?

Why computers are special devices

“I think there is a world market for maybe 5 computers.”

This is a well-known quote attributed to Thomas Watson, long time CEO of IBM, though there is a good chance he never said it.  

At any rate, we now live in a world with billions of computing devices and billions of people own one. Why did this prediction turn out to be so wrong?

To see why the answer isn’t so straightforward it is important to note that the mid-twentieth century wasn’t the first time people had developed computing devices. When we look back, we see that there was for example the Antikythera mechanism used for calculating the motions of the Moon and the Sun. Then there was this amazing device that was used to predict the tides. These were useful computing devices, but they were used for obscure purposes and never achieved more ubiquity than a special purpose manufacturing device would today.

And just like computing devices that came before it, the first modern digital computer ENIAC was also used for an obscure purpose - computing artillery firing tables. But unlike earlier computers the improved descendants of this device became ubiquitous consumer products with many industrial uses.

What was different about this device?

What did ENIAC actually do? It took sequences of simple instructions together with some additional input and executed them. The simple instructions came from a small fixed set that didn’t include much more than arithmetic, comparison and writing and loading from memory.

This may not seem like much, but it gave ENIAC a property that is not much remarked on today but was considered significant by early computing pioneers. That property is called computational universality.

What the early computing pioneers understood was that while the instruction set might be very simple, if you picked the right sequence of instructions, you could make a computer like ENIAC act like any other special purpose digital computer.

Programmed with the right set of instructions ENIAC could have acted as if it was the Antikythera mechanism. Program it with a different set of instructions and it might act as the tide computer. Computers like ENIAC and its descendants are a kind of shapeshifters that have the capacity of acting as any special purpose computer if they are programmed right.

Your laptop retains this shapeshifting ability of its predecessors. It can act as a word processor, game console or a music player and much else – even though physically it is the same screen, keyboard and electronic chips whatever application currently happens to be running on it. And it doesn’t attain all these different functionalities automatically. We need to install the right applications (sequences of instructions) on it.

This shapeshifting ability – computational universality – is a part of what makes computers so useful.

It is the reason why there is a software industry, and it is one of the reasons why this industry is “eating the world”.

For it means that many special purpose devices that exist throughout the economy – or some of the parts of those devices – can potentially be replaced with computers that just run special purpose code. Code that is much easier to update or change.

It also allows us to approach designing devices with novel functionalities in a whole new way. Whereas before we’d have to design the entire physical device, manufacture many copies of it and then put them in boxes and ship them all over the world, now you can design a piece of code that will run on a physical device whose functioning you don’t even really need to understand. There is nothing to manufacture – other people have already manufactured and delivered the physical computers. You just need to send the code over the internet. Indeed you might not even think of this whole process as designing a new device, merely a new “application”. In short, it allows us to (in many cases) move away from designing devices to designing right sequences of instructions for their core functionalities.

The massive change this has brought about to the development, production and distribution of all kinds of products is one of the main reasons why computers are so economically significant and have found their way everywhere. And this isn’t even taking into account their other virtues such as their amazing information storage ability, their communication capabilities (via the internet), their incredible information processing speed and low energy consumption.

Clearly this shapeshifting capability has its limits. It’s difficult to imagine what kind of software you’d have to install on your laptop to turn it into a coffee grinder.  Nor does the universality of our machines seem to diminish the usefulness of developing new computers and programming languages. The input/output devices used by our computers likewise keep changing and developing.  

It is in part because of these limitations that it’s exciting to be thinking about universality more broadly because it seems computational universality isn’t the only kind of universality that exists out there. For example, the fact that so many different organisms consist of similar cells that only differ in terms of what kind of genetic code they contain is a sign of some kind of universal capacity of our cells.

And then there is also us - humans and everything we have built and constructed. Whether it’s designing a computer chip whose features are measured in nanometers, building a skyscraper or shooting a probe out of the solar system it was all accomplished by humans ultimately using nothing other than our bodies. It seems to be the case that our bodies have a kind of universality when it comes to manipulating the physical world. (See here for some thinking in this direction.). All of this suggests there are several significant technological revolutions ahead of us that might be as significant as the proliferation of computers.

But to return to the beginning, computational universality also explains the existence of complete problems.

The concept of NP-completeness is generally attributed to Stephen Cook and Leonid Levin but neither used the term “NP-completeness” when first describing the idea. The title of Levin’s paper was “Universal Search Problems” which perhaps makes it a bit clearer what is going on.

Indeed given everything we’ve just described universal computers might already seem to be somewhat analogous to complete problems. A universal computer can act as any other special purpose computer and a complete problem is one whose solution can (basically) act as a solution for any other problem in the same class.

To fully explain the relationship between the two we need to look at what exactly is the computational problem that our universal computer solves. We will see it is a complete one.   

How universality leads to complete problems

When people describe computational problems, they usually say one “is given” objects that have nothing to do with computers and needs to do something with them. In the example above for instance we were “given a social network and a number”.

However, when we use a machine to actually solve an instance of one of these problems the only thing the machine is given is just a string of 0s and 1s encoded on its input device. The machine doesn’t know what meaning we ascribe to it. The machine then performs its computation and produces an output that is also just a sequence of 0s and 1s - again no matter what meaning we might ascribe to it. The pairs of input and output sequences of 0s and 1s define a function and it is really computing this function that computer scientists have in mind when they speak of “computational problems”.

This is an interesting change of meaning. The correspondence between problems as normally described and these functions isn’t one-to-one. It is in fact not even one-to-many. For there might be many ways of encoding our “given” objects as input sequences – which corresponds to different functions. Similarly the input-output pairs of any given function might have many different interpretations and correspond to several different “natural problems”.

Still the two types of problems are closely related and what we gain with this shift in perspective is that now for every computer we can clearly talk about what problem it solves – computing the function defined by the input-output pairs it produces. We will therefore talk about problems and functions interchangeably in what follows.

If we now look at one of our universal computers it takes a sequence of instructions (which again is just a sequence of 0s and 1s) and additional input. It then produces an output.

So the universal computer computes a function (solves a problem) just like any other computer. If we tried to describe it in a natural way we might say “you’re given a sequence of instructions and some additional input, what output is produced by executing this sequence of instructions on this input?”

But, because our computer is universal, this function clearly has the property that once we know how to compute it we can compute any function computed by any other computer. To use it to determine what some other computer would do on a given input we simply present it with the sequence of instructions that corresponds to that computer together with the input. Because of how the function is defined we know its output will match the output produced by that computer.

Therefore the problem of computing this function is in some sense complete for the whole class of computable functions - it allows us to compute any other computable function and it is itself computable.  

We now see how universality directly corresponds to completeness of the universal computer’s associated problem. However, how does this explain why all of the other classes mentioned above have their own complete problems?

The complexity classes mentioned above do not contain all computable functions. They are collections of problems grouped together based on whether there is a computer that can solve them while also not using too much of a particular resource. The resource can be time, memory or other things.

The way we obtain complete problems for those classes is by taking our universal computer and modify it slightly. To obtain a problem complete for the chosen class the modification needs to handicap the machine somewhat, ensuring it can only solve the problems in our target class and not those that lie outside it. At the same time the modification needs to ensure that the machine never uses too much of the class specific resource itself.

The details of how this can be accomplished vary from class to class but there is a basic idea that works for all of them. Our modified universal computer will take a sequence of instructions and input just as before. However in addition it will also take a number that tells it how much of the class specific resource the sequence of instructions is allowed to consume. It will then execute the sequence of instructions while keeping track of how much of the target resource has been consumed. If that consumption ever exceeds the given limit it will stop the execution and return an arbitrary output.

In this way our modified computer can still solve every other problem in this class, since it will never interrupt the execution for sequences of instructions that don’t violate the resource constraint. And since it is generally possible to execute a sequence of instructions and keep track of the resources it consumes without much overhead it means that the simulation itself will stay within the resource constraint. Hence the problem solved by this modified computer will be complete for the chosen class.

This, then, is how universality of computation explains the existence of complete problems. For virtually any class we might define there will be a way of handicapping the universal computer such that it is still able to solve all of the problems in the class while at the same time not breaking the class specific resource constraint.

We can now see that the existence of complete problems is a direct result of one of the core features of computers that also makes them relevant to the real world.

There is however one further question one may ask – why do so many natural problems seemingly about objects that have nothing to do with computers also turn out to be NP-complete?

And that… is a story for another time.

Thanks to David Deutsch and Bryan Kam for reading drafts and suggesting improvements.