John Nash and Louis Nirenberg have jointly won the 2015 Abel Prize for their work on partial differential equations (PDEs). They did not write any joint papers, but Nirenberg evidently got Nash excited about David Hilbert’s 19th problem during Nash’s frequent visits to New York University’s Courant Institute in the mid-1950s. Nash in return stimulated Nirenberg by his verbal approach of barraging a problem with off-kilter ideas. The Norwegian Academy of Sciences and Letters recognized their ‘great influence on each other’ in its prize announcement.
Today we congratulate both men on their joint achievement.
Hilbert’s 19th problem asked whether all solutions to certain partial differential equations must be analytic functions—that is, expressible as power series on local neighborhoods. Enough progress had been made since the 1930s that the remaining task could be likened to building a short road bridge without central stanchions or much room below for support. If you just shoot the road across it is hard to maintain the level needed to reach the other side. But if you aim up then you create more room to make an arch for best support.
The level known before Nash went to work—and Ennio De Giorgi slightly earlier in Italy—was that solutions to Hilbert’s equations gave a property on second derivatives (pardoning a negligible set of points with discontinuities or other bad non-differentiable behavior) that was insufficient. The support structure on the other side of the bridge needed some kind of continuity condition on the first partial derivatives. The task was aiming at a condition low enough to prove but high enough to land where needed on the other side. This makes us wonder whether we have similar situations in computational complexity without fully realizing it.
Nirenberg is one of few surviving researchers who worked on the Manhattan Project—in his case, on a part that had been contracted to Canada’s National Research Council in Montreal. Richard Courant’s son Ernst was a co-worker and suggested NYU as a destination for a Master’s, which led to doctoral work and affiliation there. For his PhD thesis he completed an attack by Hermann Weyl on the problem of embedding the 2-sphere equipped with any Riemannian metric having positive Gaussian curvature into as a convex surface with the standard Euclidean metric so that paths of corresponding points have the same length under the respective metrics. With Louis Caffarelli and Joseph Kohn he gave what are still considered the most stringent restrictions on possible singularities in solutions to the Navier-Stokes equations. He is acclaimed as the grand master of enduringly useful inequalities, which he said he “loves” more than equations.
The basic definition for a function to be continuous is that for every and there exists such that whenever , . Actually, a more basic definition is that for every open subset of , is open as a subset of , but we are presupposing metrics on and so that is defined for each.
If for every there is a that works for all , then is uniformly continuous. In much of real or complex analysis this is the strongest uniformity condition one needs. It comes for free if is compact. We can postulate a mapping sending to :
However, this still does not articulate a numerical relationship between and . It does not guarantee differentiability, much less that the first derivatives be continuous.
The key conditions have the form
where and are real constants. If and then is a contracting mapping. Contracting mappings can be called fellow-travelers of Nash’s work. Nash used the Brouwer fixed-point theorem to prove his famous theorem about equilibria in non-zero-sum games, but one can also use a more-general fixed-point theorem together with contracting mappings. Matthias Günther found an alternative proof of Nash’s equally great embedding theorem for Riemannian manifolds into Euclidean space via contracting mappings.
If and is arbitrary, then satisfies a Lipschitz condition, named for Rudolf Lipschitz. Although Lipschitz conditions are commonly available and frequently useful, they were still too high to aim for this problem. What De Giorgi and Nash accomplished was showing that things could work with any appropriately given or chosen . The criterion with allowed is called Hölder continuity, named for Otto Hölder.
Hölder continuity turned out to be the key for Hilbert’s 19th. The proof again was like building a bridge. For any instance of Hilbert’s equations, one could take high enough and find to make the inequality work. Given any (and ), analyticity could be shown to follow. I wonder if we can solve open problems in computer theory not by attacking them directly but by trying to set up this kind of proof structure.
Continuity and Containment
Applying this idea could be as simple as the condition for saying one complexity class is contained in another class . Consider the statement
where the classes are represented by standard computable enumerations of poly-time NTMs and of poly-time DTMs, respectively. The enumerations are nondecreasing with respect to code size. In terms of those machines, the statement is:
We can strengthen this by insisting that be given by a computable mapping of :
Thus a complexity class containment involves a mapping between “spaces” of machines. We can ask what further conditions such a mapping may or must meet. If we start with machines and that are “close” in some respect, how far apart can the machines and be?
Because has complete sets we get some further properties for free. If then there is an such that . The mapping from executes the reduction to and composes its output with to get such that .
It is important to note that although inputs of length given to are expanded by the reduction into formulas of size more than linear in which are input to , the code of simply embeds that of and and so has size linear in . Moreover, if we weaken the mapping condition to say
where means that is finite, then we can employ Leonid Levin’s universal search algorithm to write the code of in advance. This ensures that the code expansion from to has a reasonable additive constant. In any event, with respect to the ‘metric’ of code size we can deduce a kind of Lipschitz condition: for all :
And with respect to running time, although that of can be astronomical (as we noted in last year’s post), it is still for some fixed . The running time of does expand inputs into formulas of size (the tilde means ignoring polynomials in ), which makes an overall runtime of . Rather than use “” for exact runtimes, let us ignore more than just factors by defining a function to be if for all ,
What we’d like to do take two machines and —deterministic or nondeterministic—that have runtimes in and , respectively, and define a distance in terms of and . We’d further like to arrange at least that under the hypothesized mapping ,
perhaps with . This uses the putative runtime of to create an analogue of a Hölder condition.
If we define the metric simply on the exponents as then we get a Lipschitz condition. The running times of and become and , so their -distance is (at most) . However, we would like to involve quantities like “” and “” or something else that is exponential in and/or in the metric. We could try , but then to get even a Hölder condition on the mapping we are seeking such that
This is not valid without further qualification because is possible, among other things. We would be interested to find a reasonable metric based on running-time and/or program size that gives a Hölder but not Lipschitz condition.
Can happen anyway with a Hölder or even Lipschitz condition under a metric like ? It does with an oracle. The construction giving
basically maps each oracle NTM to an oracle DTM that simply bundles the translation of the code of into a formula into the oracle queries, and so has the same polynomial running time as up to log factors. Hence we can get a Lipschitz property under various distances that use the exponents in running times . This property does not necessarily “relativize,” and it may be interesting to ask what happens if it does.
Perhaps ideas like this can help probe other complexity class relations. When the classes do not have complete sets (or are not known to have them), even getting a computable embedding function can be problematic. That the concepts may be simple is not a block; the point is to find a combination of ideas that are conducive to deep uses. For instance, the maximum principle simply states that solutions to elliptic and parabolic PDEs attain their maximum on any connected open subset on the boundary of that subset. A Simons Foundation feature on Nirenberg quotes him as saying,
“I have made a living off the maximum principle.”
Of course this is similar to principles in convex optimization which Nash initially studied.
As with similar ideas we’ve posted, we’re casting about for a new handle on open problems. To quote Sylvia Nasar’s biography A Beautiful Mind on pages 218–221 about Hilbert’s 19th problem:
[Nash] had a theory that difficult problems couldn’t be attacked frontally. He approached the problem in an ingeniously roundabout manner, first transforming the nonlinear equations into linear equations and then attacking these by nonlinear means.
At worst we can pass on advice from De Giorgi, who narrowly beat Nash to the solution with a markedly different proof:
“If you can’t prove your theorem, keep shifting parts of the conclusion to the assumptions, until you can.”
Wikipedia’s bio of De Giorgi cites this from a MathOverflow thread titled “Should one attack hard problems?” that leads with
Nasar finishes her account by addressing the “shock” of De Giorgi’s earlier proof on Nash, quoting Peter Lax that when the two met at Courant in 1957, “it was like Stanley meeting Livingstone.” She puts more blame for Nash’s subsequent troubles, quoting Nash himself, on “his attempt to resolve the contradictions in quantum theory.” Which we have also been guilty of promoting. Oh well.
Can such ideas of continuity, metrics, and more broadly topology help to gain insight about complexity classes?
[typo fix: oracle NTM to oracle DTM, P_j –> P_k consistently, some other word changes]