Analog computation

This post is a quick precis of something that I hope works out a little longer. There has been, over the years, some amount of research on the complexity theory of analog computation (i.e., using analog devices with no quantization or digitization, which operate in continuous time over the real numbers). There is not, as yet, a good and complete theory of this, but some key recent papers that a person could start with are found in the book New Computational Paradigms (Springer 2008).

One question that continues to be debated is whether analog algorithms have the same constraints or lower bounds on complexity as digital algorithms computing the same results. In the most extreme view, it has been suggested that analog methods could be used to solve NP-hard problems quickly, perhaps in polynomial time. Some papers have analyzed this question, and the results so far appear to be negative. For example, a paper posted online by Warren Smith of NEC Corp. (1998) showed that in order for the above suggestion to hold of a particular kind of physical computer (a "plane mechanism"), some other implausible things would have to be the case as well.

OK, so maybe we cannot go all the way from NP-hard to P. But this doesn't in any sense prove that the lower complexity bounds are exactly equal. There are plenty of digital computations which, while not NP-hard, are still crappy in practice because they involve some large power of the input. What good is polynomial time when the algorithm's average case complexity is O(n^82) for instance?

Why is all this important? Well, cognitive science entertains a wide array of computational models, which are usually being proposed as "cognitively plausible" in some vague sense. So now there are debates about how tractable should a simulation need to be in order to seem cognitively plausible. But, all the simulations are digital. Meanwhile, the brain is not digital, it is some sort of analog system. I think that debaters need to take care over this mismatch, because there is no clear correspondence between the complexity of a digital computation and the complexity of an analog computation accomplishing the same task.