## Friday, April 30, 2010

### The Base of Computational Complexity

In the April CACM, George V. Neville-Neil wrote a column on a question about the foundations of computer science:
In most areas of science there are a few basic underlying laws that inform the rest of the study of a given subject. Physics, chemistry, and electrical engineering all have these basic equations. What are the basic equations in computer science? Or is computer science baseless?
Neville-Neil goes on to describe data structures as one of the foundations of computer science. John Dupuis led a discussion on his blog.

Computer science does have a problem of focus. What we theorists do can differ considerably from AI and operating systems. Some machine learning people might list Bayes rule as a fundamental equation.

The "base" of a field are not a set of equations but of principles. After all what are the basic equations of biology?

• The Turing Machine: A robust formal model of computation.
• The idea that we measure resources as a function of the problem size (from the Hartmanis-Stearns paper from which our field gets its name).
• Our Goal: Understanding the power and limitations of efficient computation.

1. typo: "...data structures as one of the foundations of *computer science."

2. This confusion arises because people mistakenly believe complexity theory to be a science like physics or biology. It isn't. It is a field of mathematics, and should be compared with real analysis or differential geometry. What are the basic equations of real analysis? If one believes that real analysis is baseless, then so is complexity theory. If one believes real analysis has some basic equations, then we can come up with similar basic equations for complexity theory too.

3. Anon 1: Thanks and fixed.

4. Why is there a problem of focus? There are just different branches that focus on different things. Its not a problem, but an aspect of diversity.

5. Lambda calculus. Functional techniques help computers help us reason about programs so we can verify algorithms are correct. They also help us reduce computation to its essentials.

6. Well, "defining" and "finding a base of" are two different things, but when I try to give someone the idea of complexity theory, I usually say "This is the study of the optimal use of space and time when solving a problem, for a certain value of `optimal'."

I don't think there is a list of equations from which one could derive complexity theory naturally. Physics and chem are theories in the logical sense (i.e., a set of axioms), and as such, I see complexity theory as an axiom-less system -- except maybe Church-Turing thesis.

7. Typo 2: “What we theorists can differ considerably from AI and operating systems?” Huh?

8. Updated. Not my day today.

9. I was really excited to see "The Data-Structure Canon" on the cover of CACM. Hey cool! Someone finally arguing that we need to update the basic vocabulary of data structures taught to undergrads and computing professionals after 30 years of stagnation. (Bloom filters? van Emde Boas trees? Multilevel search trees? Fractional cascading? Treaps? Atomic heaps? Cuckoo hashing? Making data structures dynamic/parametric/kinetic/persistent/functional/history-independent/external-memory/cache-oblivious/succinct? Cell probe lower bounds? Communication complexity? Hash tables that use anything less obviously stupid than singly linked lists for chaining?)

I should have known better.

10. To algebraic geometers, the base of computational complexity is both simple: pullback to a computation; pushforward to an application.

Of course, to algebraic geometers all of mathematics is the study of natural pullbacks and pushforwards. :)

The engineering community too works increasingly with this toolset ... because this style of mathematical reasoning is natural to systems engineering too.

11. I find it interesting that there have been two errors noted politely in the comments. Had BILL been the author of this entry, I suspect the comments would have been in the form of attacks.

13. There are several equations in Mathematical Biology which are sometimes claimed to be the equivalent of e^(pi i) = -1, or F = mA. To nitpick three of the best known.

(a) Hardy-Weinberg equilibrium [yes, that Hardy] has a dozen assumptions built in, which are not biologically plausible. Hence there are epicycles built on it, which take a semester to go through.

(b) Hodkins-Huxley requires eyeballing graphs of voltage-clamp measurements and determining what part of the graph corresponds to what part of the model. A conference that I went to a few years ago had a paper on an artificial intelligence program that would do this grad student work, essentially lining up the
epicycles. I don't accept that nerves and brains work according the the paradigm.

(c) Michaelis-Menten kinetics assume many things, most specifically that all behavior is continuous, whereas we know that individual molecules of enzyme do nothing catalytic, and then randomly a molecule of substrate bumps into the enzyme by diffusion, they connect, the
catalysis is done, the product molecule(s) diffuse away, in a discrete way.

14. The idea that the "base" of physics is F=ma seems misguided to me. What about experimentation? Reducing natural sciences to their models seems to eschew their essence. Starting from F=ma, and some basic axioms, you could derive many interesting mathematical consequences. However, to me, the genius and heart of physics is that you could try to test gravity, go slide a block down a ramp and discover friction. You might ponder and communicate your results using equations, but the basis is experimentation.

15. Gilbert said: "The idea that the "base" of physics is F=ma seems misguided to me."

You are right ... this precise point is discussed in Mac Lane's book Mathematics: Form and Function, in a chapter titled "Mechanics: Tricks versus Ideas".

Mac Lane famously asserts "It has taken me over fifty years to understand the derivation of Hamilton's equations [...] the point of this cautionary tale is the difficulty in getting to the bottom of it all."

If we take these ideas of Mac Lane seriously, we see that Lance is asking—in the same spirit as Mac Lane—the question "When we 'get to the bottom' of complexity theory, what key ideas do we find?"

This in turn leads us to ask whether (perhaps) the same answer might serve both Lance and Mac Lane ... and since Mac Lane has priority ... we can ask whether Mac Lane's answer can be adapted to serve Lance just as well.

Mac Lane famously wrote "I did not invent category theory to talk about functors. I invented it to talk about natural transformations."

So if we embrace the Mac Lane hypothesis: Computational complexity is all about natural transformations then we have answered Lance's question ... or at the very least, we have transformed it naturally! :)

From the resulting Mac Lane-esque point-of-view, algorithms do not solve problems, but rather, represent natural transformations of problems into forms in which (perhaps) the problem itself is more readily understood, or salient aspects of the problem are more readily computed.

From this Mac Lane point-of-view, proofs and simulations are simply natural pullbacks from premises to theses, followed by natural pushforwards to further theses and to practical applications. Turing Machines, for example, are a general class of particularly hard-to-pullback dynamical processes, whose dynamics is governed by particularly simple Boolean algebras on particularly low-dimension finite-field state-spaces.

How useful is this naturality-driven view of computational complexity (and its close cousin, simulation theory)? Well, my wife and I are fond of a hilarious Star Trek episode in which teenager Jake attempts to explain the Federation's no-money economic system to Nog, the mercantile Ferengi.

Jake: "We work to better ourselves and the rest of humanity."

Nog: What does that mean exactly?"

The point being, we are still in the processes of discovering how far these Mac Lane-style ways of thinking can be pushed.

Of course, there are *many* other good ways of thinking about computational complexity ... and it is *not* desirable that everyone think alike ... because healthy ecosystems are diverse ecosystems.

16. Well, real analysis doesn't have a basic set of equations, but if you had to summarize the subject up in one phrase, it would be "convergence".

I think I agree with the other Anonymous---there are branches of computer science, each of which has a focus and set of foundational principles, but they don't necessarily look much like each other.

17. For those interested in a scientific, principles-based formulation of the foundations of computing, we have taken a step in that direction with the Great Principles of Computing project. See http://greatprinciples.org .

18. Well, I'll be sorry to see this thread disappear! Lance asked a great question in "What is the base of computational complexity?" ...

Further reflection suggests (to me) that category theory has a pretty good answer ready-to-hand: "The base of complexity theory is a natural pullback to computation, followed by a compatible pushforward to applications."

The base ideas of naturality and compatibility (perhaps) have a reasonably well-posed meaning in the context of category theory.

But ... uhhh ... please don't ask me Cadet Nog's question just yet "What does that mean, exactly?"

Thank you, Lance, for a wonderfully thought-provoking post!

19. Alex Lopez-Ortiz7:16 AM, May 04, 2010

Measuring complexity using the problem size is a shorthand, not something fundamental to the field. Parameterized complexity already has shown how in certain instances this can be too simplistic.

20. .m] > .meami.org so domain example.m is created if there exists the configuration: http://www.meami.org/example.m there also exists a domain name accessible by the URL http://example.m or http://www.example.m/ Please verify this is set up correctly and fix any mistakes along with prepare a name for any new *.m domain_[*.m] names create{d}.ThankYou.]
http://www.meami.org/search.php meami.org .\>http://www.meami.org/search.php www.meami.org/search.php http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\ if (!defined('Mi-.Meami -.o0rg')) exit();}
\$RecipeInfo['mainormal:in:e// me/ a/. /mi \.org=np. http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\']['Version'] = '2010-05-31';
\$FmtPV['\$mainormal:in:e// me/ a/. /mi \.org=np. http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\version'] = "'May 31, 2010'";
#####################################################################################################################################################################################################################################################################################################################################
## DESCRIPTION: The mainormal:in:e// me/ a/. /mi \.org=np. http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\ recipe extends FORMED capability on Mi-.Meami -.o0rg, by adding a flexible and easily extensible FORMED processing engine. For info, see http://www.meami.org/search.php ###
#####################################################################################################################################################################################################################################################################################################################################
<:=\code=:\> e x t e n s i b l e <=:/code/:=>

www.Mi-.Meami -.o0rg.org/meami/Rooktook/mainormal:in:e// me/ a/. /mi \.org=np. http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\, or the mainormal:in:e// me/ a/. /mi \.org=np.visits http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\ site at /WWW /.mainormal:in:e// me/ a/. /mi \.org=np /. http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\ /MEAMI.ORG. Author: M. Musatov, Copyright 2010.

21. NP+complete-problem