I recently stumbled upon a fascinating talk by the physicist Nima Arkani-Hamed on the The Morality of Fundamental Physics. (“Moral” here is in the sense of “morally correct”, as opposed to understanding the impact of science on society. Perhaps “beauty” would have been a better term.)
In this talk, Arkani-Hamed describes the quest for finding scientific theories in much the same terms as solving an optimization problem, where the solution is easy-to-verify (or “inevitable”, in his words) once you see it, but the problem is that you might get stuck in a local optimum:
The classical picture of the world is the top of a local mountain in the space of ideas. And you go up to the top and it looks amazing up there and absolutely incredible. And you learn that there is a taller mountain out there. Find it, Mount Quantum…. they’re not smoothly connected … you’ve got to make a jump to go from classical to quantum … This also tells you why we have such major challenges in trying to extend our understanding of physics. We don’t have these knobs, and little wheels, and twiddles that we can turn. We have to learn how to make these jumps. And it is a tall order. And that’s why things are difficult
But what actually caught my attention in this talk is his description that part of what enabled progress beyond Newtonian mechanics was a different, dual, way to look at classical physics. That is, instead of the Newtonian picture of an evolution of particles according to clockwork rules, we think that
The particle takes every path it could between A and B, every possible one. And then imagine that it just sort of sniffs them all out; and looks around; and says, I’m going to take the one that makes the following quantity as small as possible.
I know almost no physics and a limited amount of math, but this seems to me to be an instance of moving to an external, as opposed to internal definition, in the sense described by Tao. (Please correct me if I’m wrong!) As Arkani-Hamed describes, a hugely important paper of Emmy Noether showed how this viewpoint immediately implies the conservation laws and shows that this second viewpoint, in his words, is
simple, and deep, and will always be the right way of thinking about these things.
Since determinism is not “hardwired” into this second viewpoint, it is much easier to generalize it to incorporate quantum mechanics.
This talk got me thinking about whether we can find an “external” definition for computation. That is, our usual notion of computation via Turing Machines or circuits involves a “clockwork” like view of an evolving state via composition of some basic steps. Perhaps one of the reasons we can’t make progress on lower bounds is that we don’t have a more “global” or “external” definition that would somehow capture the property that a function F is “easy” without giving an explicit way to compute it. Alas, there is a good reason that we lack such a definition. The natural proofs barrier tell us that any property that is efficiently computable from the truth table and contains all the “easy” functions (which are an exponentially small fraction of all functions) must contain many many other functions (in fact more than 99.99% of all functions) . It is sometimes suggested that the way to bypass this barrier is to avoid the “largeness” condition, as for example even a property that contains all functions except a single function G would be useful to prove a lower bound for G if we can prove that it contains all easy functions. However, I think that to obtain a true understanding of computation, and not just a lower bound for a single function, we will need to find completely new types of nonconstructive arguments.
Windows On Theory 
I like this idea a lot.
I guess the big question is whether there’s a notion of duality on the space of languages—or maybe the space of algorithms—that sheds light on computation. For languages, there’s an annoyingly natural notion of duality given by the standard Fourier transform on {0,1}^n. Obviously, this is an extremely useful tool in the analysis of boolean functions, but it doesn’t seem very useful for your purposes. This gorilla in the room makes it hard to think of other notions though :).
Thanks! I really have no clue as to what such an object could be. When you restrict yourself to convex relaxations you have a nice notion of duality where certificates can be interpreted as computational Bayesian probabilities, but for general algorithms we don’t have such nice objects
We absolutely have such objects. There is a known “duality” between infinite families of finite sets of strings (used to test if a given circuit computes a function) and infinite families of Boolean circuits (computing a function). In particular finding good “test sets of data” is eq6ivalent to proving circuit lower bounds. See https://people.csail.mit.edu/rrw/itcs-single-column.pdf
It’s hard to mentally work with this formulation though, even if it has turned a universal quantifier into an existential. One can recover some old lower bounds by designing “bad” sets of inputs, but at this point in time it seems far easier to reason about lower bounds by simply assuming the opposite and using algorithmic thinking to obtain a contradiction.
Many notions of “dual space” of some space X in mathematics take the general form of “all nice functions from X to some simple target space Y”. E.g. the dual X* of a vector space X is the space of all linear functionals on X. The Fourier characters are continuous homomorphisms into the circle (i.e. the Pontryagin dual). I think there is a way to see polarity in geometry (which is closely related to duality for convex optimization) in this way, although I am not sure. In general the philosophy here seems to be to study an object by basically forgetting about it and studying its morphisms instead.
So maybe the dual of a complexity class will be a set of functions from languages in the class to some simple target space, maybe just {0,1}. But what is a “nice function”? An efficiently computable one? How efficiently? Can you do this in such a way that if you take the double dual you go back to the original complexity class?
Thanks Sasho.
I am guessing there isn’t going to be a super direct analog of Fourier transforms that we just missed, but perhaps there is a way to generalize these things further.
There is of course also the question of what objective such an “external definition” should satisfy.
Do we want to have a conjectural correspondence between the “internal” and “external” definitions that implies a lot of interesting conditional implications?
Or maybe a proven correspondence that can serve as a pathway to proving unconditional results?
Or maybe a research program of proving both the correspondence and the implications?
Wouldn’t the term “variational” (https://en.wikipedia.org/wiki/Variational_principle) be a better choice than “external”?
Also, can you explain the difference between what you’re looking for and something like descriptive complexity?
I might not be understanding either term very well, but I viewed the term “external” as a more general term of any setting when you describe an object by embedding it in a much larger space.
Descriptive complexity theory does have some of this flavor, but I think it is not as radically different viewpoint ,and hence does not have as far reaching applications, as to the dream version of an external definition.
As one possible approach in the direction I think you’re proposing, I would suggest considering the topological description of computation given in part 2 (“Preliminaries”) of this paper (http://lamport.azurewebsites.net/pubs/abadi-existence.pdf) by Leslie Lamport and Martin Abadi. They describe computations (i.e., executions) as sequences in a topological space with an equivalence relation called “stuttering equivalence”. An algorithm-like concept is just a set in this space (comprising of all possible computations of the algorithm), and an actual algorithm (or a “realizable” algorithm) is given as a pair of sets, S and L, such that S is closed and L is dense (S represents a safety property and L a liveness property), where the set of computations of the algorithm is the intersection of S and L. The approach comes not from TCS but from formal methods; nevertheless, it may be interesting to consider.
Thanks!
there is a simple measure of complexity of functions, its simply “minimum circuit size” (MCSP). however, this function is extremely complex to study. there is not a lot of theoretical work on it and not much experimental work on it either. both must be leveraged. (think there are some unnatural avoidances of one area by practitioners of the other, ie experimentalists avoid theory & theorists avoid experiments.) suspet MCSP likely has a fractal structure that has not even been discovered yet. re natural proofs, deep stuff and hasnt been surpassed in 2 decades. to me it seems to hint at the limitations of any methods that try/ attempt to prove complexity class separations via “distributions”.
oh and re quantum mechanics, after thinking about it/ analyzing it very deeply for several decades, now think it is not being properly understood in current conventional wisdom (as einstein conjectured/ asserted) now solidified into dogma after nearly a century of congealing. the problem hinges on a misunderstanding of emergent behavior and an artificial distinction between quantum and classical behaviors. we are now only recently finding that purely classical systems can lead to a quantum-like formalism through emergent behavior. the devil is in the details. encourage hard-core researchers to drop by my blog or contact me for more details. believe a 2nd quantum revolution even more wondrous than the 1st is in the cards/ right on the verge of materializing 🙂
If I understand correctly, I think that Toffoli has some work that tries to address this question (or at least poses some related questions.) See, e.g., his 1998 paper “Action, Or the Fungibility of Computation”
Thanks Bruce! I only skimmed it so far but it does look like a fascinating paper (the PDF is available on citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.2410 ).
The questions he raises seem possibly related to computational notions of entropy, though I am not yet sure if there is a precise connection.
The basic intuition is very appealing, but I don’t know whether it would be possible to make anything concrete from a computability/complexity perspective.
The basic ideas are very appealing, but I think that one needs more than a variational principle. (Not that I would know what I am talking about) but the efficiency of the Hamiltonian approach relies on continuity–the perturbations of an optimal path will be almost optimal. One can do similar stuff with discrete optimization _ I think this is what Feynman did with looking at all transitions — but then one looses exactly computational efficiency, the very thing we are trying to model.