Superstring theory is widely considered a leading candidate for a theory unifying quantum gravity with the other forces of nature. Given a choice of vacuum configuration, including a choice of Calabi-Yau manifold and other mathematical data characterizing the extra dimensions, one can in principle compute all the parameters of fundamental physics. However, recent developments suggest that the theory has a vast and complex landscape of consistent vacuum configurations, perhaps numbering 10^{500} or more. While this development has led to solutions of outstanding physical problems, such as the cosmological constant problem, it could also make the search for the "right" vacuum configurations, which could describe our universe, extraordinarily difficult. We will discuss the nature of this problem, the efforts now being initiated to attack it computationally, and evidence that it may be intractable (NP hard). Even if so, there are strategies for making testable predictions. Alternatively, some physicists have suggested that dual formulations of string theory might solve the problem directly; if so, this might lead to new approaches to solving certain NP hard problems. Along the way, we discuss related physical approaches to understanding and solving intractable problems using ideas from statistical mechanics and quantum computing. The talk is non-technical and intended for a general mathematically oriented audience. Based in part on work in progress with Frederik Denef (Rutgers).