Tuesday, January 31, 2006

NP-hard landscape problems

The topological conference has attracted a lot of great mathematical physicists and mathematicians. I will report on Robbert Dijkgraaf's talk in a moment.

Frederik Denef who is one of the young big shots in the topological landscape interface allowed me to inform you that he and Michael Douglas are completing two papers about the NP-difficulties of locating the right vacua in the landscape.

If I understand well, "N" denotes the number of different fluxes, and they can rigorously prove that you need a longer-than-polynomial time in "N" to go through all the configurations of different fluxes in order to identify one with plausible values of quantities such as the vacuum energy.

You know that it is hard to prove that some apparently difficult problems are NP (non-polynomial), which is the source of the open questions about the so-called NP-completeness, so I am curious how the proof roughly looks like.

The philosophical conclusion is obvious: you should not even try to find the right vacuum because the required time will exceed the recurrence time of the Universe. Peter Woit and his gang will probably have some new exciting material to talk about. ;-) You may guess that my conclusion is that if the NP-hardness is true, then the class of the vacua is likely to be physically irrelevant.

In another paper, they study cosmological consequences of the fact that Nature cannot "compute" these things in a polynomial time either. Expect that the text above contains certain inaccuracies because there were no formulae written down in the discussion.

Terminological correction by Andy Neitzke:

I think NP is not "non-polynomial" but rather "nondeterministic-polynomial" -- a problem in NP is one which can be solved in polynomial time by a computer which is allowed to branch nondeterministically. So every problem in P is in NP. A problem is called NP-complete if it is in NP and if furthermore every problem in NP can be reduced to it in polynomial time. From that description it might sound amazing that there are any NP-complete problems, but there are -- and there are some "standard" tricks for proving that a given problem is NP-complete. The deep open question which nobody knows how to solve is whether NP = P, i.e. whether all NP problems can actually be solved in polynomial time even by a deterministic computer.

If I remember right, "X is NP-hard" means that every problem in NP can be reduced to X in polynomial time, but X itself might not be in NP.


  1. I think any one with some basic science background should know something about the most important computer science problems. The NP = P? problem is one of the seven milinium math problems and there is no excuse not knowing what it is.

    I recommend reading the book "The New Turing Omnibus", which contains some very easy to read materials explaining the NP complete problem and much more. It should be on the book shielf of every one who wants to claim knowing a bit of math.

    But whatever the outcome of NP=P? is, it has no impact on the string landscape problem. 10^500 simply far exceeds anything that could exist in this universe and so any theoretical discussion whether that is a computable problem or not should not even start.

    The universe really is not that complicated. You constructed a model that far exceeds the complexity of the universe itself. The God now wishes that he had learned super string theory before he went on to create that pity little 4-D spacetime.


  2. Dear Lubos,

    you should not even try to find the right vacuum because the required time will exceed the recurrence time of the Universe, naturally, but you can try to find seemly interference of the superposition of all quantum-consistent vacuum by hypothetical quantum computer, right ?

    Best, planckeon