Complexity is the study of how difficult calculations are. Some problems take a small amount of time to solve and some take much longer (using a computer). Complexity theorists study the differences in a mathematically rigorous way.

There are many arguments I commonly hear which I think of as dubious. Amongst these are some where the crucial error comes from a lack of understanding of the relative hardness of performing different calculations.

I shall give examples of instances where people fail to take complexity theory into account.

* In science different kinds of phenomena are explained using different scientific theories (from Quantum mechanics through natural selection to social choice theories). Often its claimed that all you need to understand other aspects of reality is the base theory. Strictly it is the case that (assuming we have a fundamental theory that is computable) we can calculate everything that happens in the world from the state of the world as it is now (albeit in probabilistic terms). However the complexity of those calculations make it effectively impossible to do in many possible worlds (possibly including ones based on quantum mechanics). This means realistically we do need other levels of science to understand the world.

* Any mathematical function from the integers onto the integers that can be performed can be reversed. It used to be considered to be impossible for two people to talk in public (without having met before) and communicate information privately. Strictly speaking it is always possible, given enough time, to figure out what it is they were talking about. There may exist (assuming a certain prominent mathematical conjecture) functions that are much easier to perform than to do reverse (the mathematical equivalent of scrambling an egg). This would allow people to talk in public without eavesdroppers understanding them. Large sections of our financial institutions depend on this mathematical conjecture being true (or at least not nastily false). It took some particularly brilliant mathematicians to see this was the case when the common sense view made it seem impossible.

* In order to protect private data we used to keep sensitive information in locked filing cabinets, keep the filing cabinets within corporate offices and employ only people who've been carefully vetted. Some (including prominent politicians) have argued that in the Internet age we need only adapt the policy to include digital locks on the digital filing cabinets and company networks. This is dangerously flawed thinking. The complexity of accessing a piece of private information (illegitimately) has gone right down. Copying an entire warehouse full of private data would take months (before the Internet). Today if the files are centralised the same task can be accomplished in hours, sometimes minutes.

* It has been argued by some neuroscientists that we will not be able to read people's minds even if we can trace the firing of their neurons explicitly. The argument goes that the inner workings of people's minds are probably unique to them (almost certainly true), the minds have many things going on at once in parallel (true) and that we will therefore not be able to come up with a sensible way of understanding what the neuronal signals mean (hmmmm). The important question is "Can you hide what task you're doing by performing it in an incredibly idiosyncratic way even if your enemies can see everything you do". Well, this is essentially equivalent to finding a way to hide what a program is doing on your computer from someone who can watch its every calculation. No one has found a way to do this (its possible to make it a little harder though). Many cryptographers think its impossible to do. Certainly its very unlikely that the brain is set up to do this (Why would it evolve this way?). This means it is likely that knowing exactly what neurons were firing in a brain would tell you what that brain was thinking.

I hope thats given you some indication of the value of this new area of research!

## Comments