Wednesday, February 08, 2006

String theory and NP-hardness

Via Peter Woit, a paper that proves the NP-hardness of a problem relating to the (in)famous string theory "landscape". Specifically,
We study the computational complexity of the physical problem of finding vacua of string theory which agree with data, such as the cosmological constant, and show that such problems are typically NP hard.
I mention this because it appears to be among the first few examples of NP-hardness impinging on the frontiers of physics. The paper has a very lucid explanation of some of the places in string theory where NP-hardness and other complexity notions pop up.

Some skepticism as to the relevance of this proof, here.

Disqus for The Geomblog