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.