Complex Landscape

Last week, there was a paper by Fred Denef and Michael Douglas that studies the computational complexity of problems one is likely to encounter invesitgating the landscape according to them. Once again a paper by these authors that studies a well defined mathematical problem and not just contains vague speculations of various extend as it is not uncommon amongst landscapers. The obvious point for the reader to make up his mind is of course the judge the physical relevance of the abstract mathematical problem investigated.

The paper at hand contains some sort of meta-discussion in that it looks at various problems one is likely to encounter once more information about string vacua is known and points out that a lot of them although solvable in finite time are practically intractable because it is likely that the computation time is astronomical because it scales exponentially with some size parameter of the problem.

A typical example is the toy model due to Arkani-Hamed, Dimopoulos and Kachru: There you have N scalar fields f_i and the total potential is a sum of potentials V_i(f_i) each depending on only one scalar and having two minima V_i^+ and V_i^- of any sign and both typipcally of Planck mass scale. The problem is to assign each of the scalars to one of its minima such that the total potential energy is of order 10^-120 M_p or to decide if such an asignment is possible.

This is supposed to be a simplification of what actually goes on in string theory and it is to decide if string theory allows of our universe for which one might assume some early cosmological dynamics would pick a vacuum with minimal positive cosmological constant at least for some part of the universe which then expands to become our visible universe.

It turns out that this toy problem is one in the class of NP complete problems which are generally assumed to have a worst case that requires computational time which scales exponentially with N making it practically intractible even for N of intermediate size.

Of course, this toy model is infinitely simpler than the full problem: The true string theory effective potential is not believed just to be a sum of individual terms but the choices of vacua of the individual fields are coupled. Furthermore, in order for this problem to make sense, the terms in the potential have to be known with an accuracy of 10^-120 which is not only unrealistic but maybe impossible given the asymptotic nature of some of the series expansions envolved.

My main objection however is that this type of investigation is premature until one has better information about the actual problem: The complexity class is only about worse case behaviour and it is well possible that there is additional information available which then renders the problem much much easier. If for example I hapen to know that the V_i^+ and V_i^- decrease exponentially with i then the decision problem is a piece of cake. Until you can be sure there is no such additional information and you really have to solve the generic problem it does not really make sense to worry about complexity.

It is well known that in many real world examples of problems which are in principle NP hard, practical instances have efficient solutions (sometimes approximate) which serve at least most purposes. For example I am always amazed how German rail can provide very good connection information not only between train stations (and there is already a large number of trains) but even at street level resolution as it contains also local public transport including busses. I heard Italians claim that they even use this web page to obtain connections between places in Italy. This is a hard problem, but that webpage works in fracitons of a second rather than the aeons that it takes a poor salesman to try out all possible connections via Calcutta. And that is because the data is more structured and there is more information available.

You could worry that these special cases with additional information are just a set of small measure in the full class of problems so one should not hope for such additional information until one has it. Well, as I said, experience shows differently.

Furthermore, what would have happend if for example the old Greeks had decided that there are myriads of phenomena in the natural world and it likely takes exponential computational power to work them out even if one knew the governing laws. So time is better invested in in practising one's harp playing than working out those laws? This is the whole point of the "unreasonable effectiveness of mathematics in the sciences" that our world is structured and there are simple laws behind everything that we have understood so far. So I would not judge it completely unrealistic to hope for additional structure that makes science tracktable even when it comes to the most fundamental degrees of freedom.