Computational complexity of the landscape. I. (English) Zbl 1113.83007
Summary: 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. In particular, we prove that in the Bousso-Polchinski model, the problem is NP complete. We discuss the issues this raises and the possibility that, even if we were to find compelling evidence that some vacuum of string theory describes our universe, we might never be able to find that vacuum explicitly. In a companion paper, we apply this point of view to the question of how early cosmology might select a vacuum.
MSC:
| 83C05 | Einstein’s equations (general structure, canonical formalism, Cauchy problems) |
| 81T30 | String and superstring theories; other extended objects (e.g., branes) in quantum field theory |
| 83E30 | String and superstring theories in gravitational theory |
References:
| [1] | S. Aaronson, Available from: arXiv:quant-ph/0402095; S. Aaronson, Available from: arXiv:quant-ph/0402095 |
| [2] | S. Aaronson, Quantum computing, postselection, and probabilistic polynomial-time. Available from: arXiv:quant-ph/0412187; S. Aaronson, Quantum computing, postselection, and probabilistic polynomial-time. Available from: arXiv:quant-ph/0412187 |
| [3] | S. Aaronson, NP-complete problems and physical reality. Available from: arXiv:quant-ph/0502072; S. Aaronson, NP-complete problems and physical reality. Available from: arXiv:quant-ph/0502072 |
| [4] | Abbott, L. F., Phys. Lett., B150, 427 (1985) |
| [5] | D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, O. Regev, Adiabatic quantum computation is equivalent to standard quantum computation. Available from: arXiv:quant-ph/0405098; D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, O. Regev, Adiabatic quantum computation is equivalent to standard quantum computation. Available from: arXiv:quant-ph/0405098 · Zbl 1134.81009 |
| [6] | Ajtai, M., (Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (1998), ACM: ACM New York), 10-19 |
| [7] | M. Ajtai, in: Proceedings of the 43rd IEEE FOCS 2002. Revised version at http://eccc.uni-trier.de/eccc-reports/2002/TR02-061/Paper.ps; M. Ajtai, in: Proceedings of the 43rd IEEE FOCS 2002. Revised version at http://eccc.uni-trier.de/eccc-reports/2002/TR02-061/Paper.ps |
| [8] | Agrawal, M.; Kayal, N.; Saxena, N., Ann. Math., 160, 781-793 (2004) · Zbl 1071.11070 |
| [9] | I. Antoniadis, The physics of extra dimensions. Available from: arXiv:hep-ph/0512182; I. Antoniadis, The physics of extra dimensions. Available from: arXiv:hep-ph/0512182 |
| [10] | Arkani-Hamed, N.; Dimopoulos, S., JHEP, 0506, 073 (2005), Available from: |
| [11] | N. Arkani-Hamed, S. Dimopoulos, S. Kachru, Predictive landscapes and new physics at a TeV. Available from: arXiv:hep-th/0501082; N. Arkani-Hamed, S. Dimopoulos, S. Kachru, Predictive landscapes and new physics at a TeV. Available from: arXiv:hep-th/0501082 |
| [12] | S. Arora, Computational complexity: a modern approach. Available from: http://www.cs.princeton.edu/arora/book/book.html; S. Arora, Computational complexity: a modern approach. Available from: http://www.cs.princeton.edu/arora/book/book.html · Zbl 1193.68112 |
| [13] | Ashok, S.; Douglas, M. R., JHEP, 0401, 060 (2004), Available from: |
| [14] | Balasubramanian, V.; Berglund, P., JHEP, 0411, 085 (2004), Available from: |
| [15] | Balasubramanian, V.; Berglund, P.; Conlon, J. P.; Quevedo, F., JHEP, 0503, 007 (2005), Available from: |
| [16] | Banks, T.; Dine, M.; Seiberg, N., Phys. Lett. B, 273, 105 (1991), Available from: |
| [17] | Banks, T.; Dine, M.; Douglas, M. R., Phys. Rev. Lett., 88, 131301 (2002), Available from: |
| [18] | T. Banks, Landskepticism or why effective potentials don’t count string models. Available from: arXiv:hep-th/0412129; T. Banks, Landskepticism or why effective potentials don’t count string models. Available from: arXiv:hep-th/0412129 |
| [19] | T. Banks, M. Johnson, Regulating eternal inflation. Available from: arXiv:hep-th/0512141; T. Banks, M. Johnson, Regulating eternal inflation. Available from: arXiv:hep-th/0512141 |
| [20] | Barahona, F., J. Phys. A: Math. Gen., 15, 3241-3253 (1982) |
| [21] | Barrow, J. D.; Tipler, F. J., The Anthropic Cosmological Principle (1988), Oxford University Press |
| [22] | Bennett, C. H., Int. J. Theor. Phys., 21, 12, 905-940 (1982) |
| [23] | Blumenhagen, R.; Gmeiner, F.; Honecker, G.; Lust, D.; Weigand, T., Nucl. Phys. B, 713, 83 (2005), Available from: · Zbl 1176.81098 |
| [24] | Bousso, R.; Polchinski, J., JHEP, 0006, 006 (2000), Available from: |
| [25] | Brown, J. D.; Teitelboim, C., Phys. Lett. B, 195, 177 (1987) |
| [26] | Brown, J. D.; Teitelboim, C., Nucl. Phys. B, 297, 787 (1988) |
| [27] | Bryngelson, J. D.; Onuchic, J. N.; Socci, N. D.; Wolynes, P. G., Proteins Struct. Funct. Genet., 21, 167 (1995), Available from: |
| [28] | Burgess, C. P.; Kallosh, R.; Quevedo, F., JHEP, 0310, 056 (2003), Available from: |
| [29] | T. Byrnes, Y. Yamamoto, Simulating lattice gauge theories on a quantum computer. Available from: arXiv:quant-ph/0510027; T. Byrnes, Y. Yamamoto, Simulating lattice gauge theories on a quantum computer. Available from: arXiv:quant-ph/0510027 |
| [30] | S.M. Carroll, Why is the universe accelerating? eConf C0307282, TTH09 (2003) [AIP Conf. Proc. 743, 16 (2005)]. Available from: arXiv:astro-ph/0310342; S.M. Carroll, Why is the universe accelerating? eConf C0307282, TTH09 (2003) [AIP Conf. Proc. 743, 16 (2005)]. Available from: arXiv:astro-ph/0310342 |
| [31] | http://www.claymath.org/millennium/P_vs_NP; http://www.claymath.org/millennium/P_vs_NP |
| [32] | The Complexity Zoo. Available from: http://qwiki.caltech.edu/wiki/Complexity_Zoo; The Complexity Zoo. Available from: http://qwiki.caltech.edu/wiki/Complexity_Zoo |
| [33] | Conlon, J. P.; Quevedo, F., JHEP, 0410, 039 (2004), Available from: |
| [34] | Cook, S., JACM, 50, 1, 27-29 (2003) · Zbl 1326.68140 |
| [35] | Dasgupta, K.; Rajesh, G.; Sethi, S., JHEP, 9908, 023 (1999), Available from: |
| [36] | Denef, F.; Douglas, M. R., JHEP, 0405, 072 (2004), Available from: |
| [37] | Denef, F.; Douglas, M. R.; Florea, B., JHEP, 0406, 034 (2004), Available from: |
| [38] | Denef, F.; Douglas, M. R., JHEP, 0503, 061 (2005), Available from: |
| [39] | F. Denef, M.R. Douglas, B. Florea, A. Grassi, S. Kachru, Fixing all moduli in a simple F-theory compactification. Available from: arXiv:hep-th/0503124; F. Denef, M.R. Douglas, B. Florea, A. Grassi, S. Kachru, Fixing all moduli in a simple F-theory compactification. Available from: arXiv:hep-th/0503124 · Zbl 1129.81065 |
| [40] | F. Denef, M.R. Douglas, Computational complexity of the landscape ii: cosmological considerations, to appear.; F. Denef, M.R. Douglas, Computational complexity of the landscape ii: cosmological considerations, to appear. · Zbl 1113.83007 |
| [41] | Deutsch, D.; theory, Quantum, Proc. R. Soc. Lond. A, 400, 97 (1985) · Zbl 0900.81019 |
| [42] | M. Dine, Supersymmetry, naturalness and the landscape. Available from: arXiv:hep-th/0410201; M. Dine, Supersymmetry, naturalness and the landscape. Available from: arXiv:hep-th/0410201 |
| [43] | Douglas, M. R., JHEP, 0305, 046 (2003), Available from: |
| [44] | M.R. Douglas, Statistical analysis of the supersymmetry breaking scale. Available from:arXiv:hep-th/0405279; M.R. Douglas, Statistical analysis of the supersymmetry breaking scale. Available from:arXiv:hep-th/0405279 |
| [45] | Douglas, M. R., C. R. Phys., 5, 965 (2004), Available from: |
| [46] | M.R. Douglas, B. Shiffman, S. Zelditch, Critical points and supersymmetric vacua. III: String/M models. Available from: arXiv:math-ph/0506015; M.R. Douglas, B. Shiffman, S. Zelditch, Critical points and supersymmetric vacua. III: String/M models. Available from: arXiv:math-ph/0506015 · Zbl 1107.32007 |
| [47] | M.R. Douglas, Z. Lu, Finiteness of volume of moduli spaces. Available from: arXiv:hep-th/0509224; M.R. Douglas, Z. Lu, Finiteness of volume of moduli spaces. Available from: arXiv:hep-th/0509224 |
| [48] | http://physics.nist.gov/cuu/Constants/energy.html; http://physics.nist.gov/cuu/Constants/energy.html |
| [49] | E. Farhi, J. Goldstone, S. Gutmann, M. Sipser, Quantum computation by adiabatic evolution. . Available from: arXiv:quant-ph/0001106; E. Farhi, J. Goldstone, S. Gutmann, M. Sipser, Quantum computation by adiabatic evolution. . Available from: arXiv:quant-ph/0001106 |
| [50] | E. Farhi, J. Goldstone, S. Gutmann D. Nagaj, How to make the quantum adiabatic algorithm fail. Available from: arXiv:quant-ph/0512159; E. Farhi, J. Goldstone, S. Gutmann D. Nagaj, How to make the quantum adiabatic algorithm fail. Available from: arXiv:quant-ph/0512159 · Zbl 1192.81064 |
| [51] | Feng, J. L.; March-Russell, J.; Sethi, S.; Wilczek, F., Nucl. Phys. B, 602, 307 (2001), Available from: · Zbl 0989.83045 |
| [52] | Ferrara, S.; Kallosh, R.; Strominger, A., Phys. Rev. D, 52, 5412 (1995), Available from: |
| [53] | Feynman, R. P., Int. J. Theor. Phys., 21, 6/7, 467-488.l (1982) |
| [54] | Freedman, M. H.; Kitaev, A.; Wang, Z., Commun. Math. Phys., 227, 587 (2002), Available from: · Zbl 1014.81006 |
| [55] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company · Zbl 0411.68039 |
| [56] | S. Geman, D. Geman, IEEE Trans. PAMI-6 721 (1984).; S. Geman, D. Geman, IEEE Trans. PAMI-6 721 (1984). |
| [57] | Geroch, R.; Hartle, J. B., (Zurek, W. H.; van der Merwe, A.; Miller, W. A., Between Quantum and Cosmos: Studies and Essays in Honor of John Archibald Wheeler (1988), Princeton Univ. Press) |
| [58] | Gibbons, G. W.; Hawking, S. W., Phys. Rev. D, 15, 2752 (1977) |
| [59] | Giddings, S. B.; Kachru, S.; Polchinski, J., Phys. Rev. D, 66, 106006 (2002), Available from: |
| [60] | F. Gmeiner, R. Blumenhagen, G. Honecker, D. Lust, T. Weigand, One in a billion: MSSM-like D-brane statistics. Available from: arXiv:hep-th/0510170; F. Gmeiner, R. Blumenhagen, G. Honecker, D. Lust, T. Weigand, One in a billion: MSSM-like D-brane statistics. Available from: arXiv:hep-th/0510170 |
| [61] | Grover, L. K., STOC, 28, 212-219 (1996) · Zbl 0922.68044 |
| [62] | L.K. Grover, Proc. 30 Annual ACM Symp. on Theory of Computing, ACM Press. Available from: arXiv:quant-ph/9711043; L.K. Grover, Proc. 30 Annual ACM Symp. on Theory of Computing, ACM Press. Available from: arXiv:quant-ph/9711043 |
| [63] | Gukov, S.; Vafa, C.; Witten, E., Nucl. Phys. B, 584, 69 (2000), [Erratum Nucl. Phys. B 608 (2001) 477. Available from:] |
| [64] | Han, Y.; Hemaspaandra, L.; Thierauf, T., SIAM Journal on Computing, 26, 1, 59-78 (1997) · Zbl 0868.68056 |
| [65] | Hawking, S. W., Phys. Lett. B, 134, 403 (1984) |
| [66] | Johnson, D. S., ACM transactions on algorithms, 1, 1, 160-176 (2005) · Zbl 1442.68065 |
| [67] | Kachru, S.; Kallosh, R.; Linde, A.; Trivedi, S. P., Phys. Rev. D, 68, 046005 (2003), Available from: · Zbl 1244.83036 |
| [68] | R.M. Karp, in: Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, Plenum, New York, 1972, pp. 85-103.; R.M. Karp, in: Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, Plenum, New York, 1972, pp. 85-103. |
| [69] | Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Science, 220, 671-680 (1983) · Zbl 1225.90162 |
| [70] | Kirkpatrick, S.; Selman, B., Science, 264, 1297-1301 (1994) · Zbl 1226.68097 |
| [71] | Kitaev, A. Yu.; Shen, A. H.; Vyalyi, M. N., Classical and Quantum Computation (1992), AMS · Zbl 1022.68001 |
| [72] | Klemm, A.; Lian, B.; Roan, S. S.; Yau, S. T., Calabi-Yau fourfolds for M- and F-theory compactifications, Nucl. Phys. B, 518, 515 (1998), Available from: · Zbl 0920.14016 |
| [73] | Klein, P. N.; Young, N. E., Approximation algorithms for NP-hard optimization problems. Approximation algorithms for NP-hard optimization problems, Algorithms and Theory of Computation Handbook (1999), CRC Press, http://www.cs.brown.edu/people/pnk/publications/1998approxOpt.ps |
| [74] | J. Kumar, A review of distributions on the string landscape. Available from: arXiv:hep-th/0601053; J. Kumar, A review of distributions on the string landscape. Available from: arXiv:hep-th/0601053 |
| [75] | A.K. Lenstra, H.W. Lenstra, L. Lovász, Factoring polynomials with rational coefficients, Ann. Math., 261, 515-534.; A.K. Lenstra, H.W. Lenstra, L. Lovász, Factoring polynomials with rational coefficients, Ann. Math., 261, 515-534. · Zbl 0488.12001 |
| [76] | Lautemann, C., Inf. Proc. Lett., 17, 215-218 (1983) · Zbl 0515.68042 |
| [77] | Levinthal, C., (DeBrunner, P.; etal., Mossbauer Spectroscopy in Biological Systems (1969), University of Illinois Press: University of Illinois Press Urbana), 22 |
| [78] | Mézard, M.; Parisi, G.; Virasoro, M. A., Spin Glass Theory and Beyond (1987), World Scientific · Zbl 0992.82500 |
| [79] | Nabutovsky, A.; Ben-Av, R., Commun. Math. Phys., 157, 1, 93-98 (1993) · Zbl 0785.53065 |
| [80] | Nielsen, M. A.; Chuang, I. L., Quantum Computation and Quantum Information (2000), Cambridge University Press · Zbl 1049.81015 |
| [81] | For an updated online list of NPhttp://www.nada.kth.se/ viggo/problemlist/compendium.html; For an updated online list of NPhttp://www.nada.kth.se/ viggo/problemlist/compendium.html |
| [82] | Papadimitriou, C., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0833.68049 |
| [83] | J. Polchinski, Introduction to cosmic F- and D-strings. Available from: arXiv:hep-th/0412244; J. Polchinski, Introduction to cosmic F- and D-strings. Available from: arXiv:hep-th/0412244 |
| [84] | Preskill, J., J. Mod. Opt., 47, 127-137 (2000), Available from: |
| [85] | J. Preskill, Quantum information and the future of physics, 2002 lecture.; J. Preskill, Quantum information and the future of physics, 2002 lecture. |
| [86] | Rubakov, V. A., Phys. Usp., 44, 871 (2001), [Usp. Fiz. Nauk 171 (2001) 913. Available from:] |
| [87] | S. Rudich, A. Wigderson (Eds.), Computational Complexity Theory, IAS/Park City Mathematics series, vol. 10, AMS, 2004.; S. Rudich, A. Wigderson (Eds.), Computational Complexity Theory, IAS/Park City Mathematics series, vol. 10, AMS, 2004. |
| [88] | Saltman, A.; Silverstein, E., JHEP, 0411, 066 (2004), Available from: |
| [89] | Sherrington, D.; Kirkpatrick, S., Phys. Rev. Lett., 35, 1792-1796 (1975) |
| [90] | Shor, P. W., FOCS, 35, 124-134 (1994) |
| [91] | P.W. Shor, Progress in Quantum Algorithms, available at http://www-math.mit.edu/shor/elecpubs.html; P.W. Shor, Progress in Quantum Algorithms, available at http://www-math.mit.edu/shor/elecpubs.html · Zbl 1075.68602 |
| [92] | L. Smolin, How far are we from the quantum theory of gravity? Available from: arXiv:hep-th/0303185; L. Smolin, How far are we from the quantum theory of gravity? Available from: arXiv:hep-th/0303185 |
| [93] | Socolich, M.; Lockless, S. W.; Russ, W. P.; Lee, H.; Gardner, K. H.; Ranganathan, R., Nature, 437, 7058, 512-518 (2005) |
| [94] | L. Susskind, The anthropic landscape of string theory. Available from: arXiv:hep-th/0302219; L. Susskind, The anthropic landscape of string theory. Available from: arXiv:hep-th/0302219 |
| [95] | L. Susskind, Supersymmetry breaking in the anthropic landscape.Available from: arXiv:hep-th/0405189; L. Susskind, Supersymmetry breaking in the anthropic landscape.Available from: arXiv:hep-th/0405189 |
| [96] | Unger, R.; Moult, J., Bull. Math. Biol., 55, 6, 1183-1198 (1993), For a review see [32] · Zbl 0791.92011 |
| [97] | Uzan, J. P., Rev. Mod. Phys., 75, 403 (2003), Available from: · Zbl 1205.81142 |
| [98] | P. Varga, Minimax Games, Spin Glasses and the Polynomial-Time Hierarchy of Complexity Classes, cond-mat/9604030.; P. Varga, Minimax Games, Spin Glasses and the Polynomial-Time Hierarchy of Complexity Classes, cond-mat/9604030. |
| [99] | Wales, D. J., Energy Landscapes (2003), Cambridge Univ. Press |
| [100] | Wegener, I., Complexity Theory: Exploring the Limits of Efficient Algorithms (2004), Springer |
| [101] | Weinberg, S., Phys. Rev. Lett., 59, 2607 (1987) |
| [102] | Weinberg, S., Rev. Mod. Phys., 61, 1 (1989) · Zbl 1129.83361 |
| [103] | Weinberg, S., Phys. Today, 31-35 (2005) |
| [104] | Weinberger, S., Computers, Rigidity and Moduli (2005), Princeton Univ. Press · Zbl 1078.53025 |
| [105] | Available from: http://en.wikipedia.org/wiki/List_of_complexity_classes; Available from: http://en.wikipedia.org/wiki/List_of_complexity_classes |
| [106] | Wright, S., Proceedings of the Sixth International Congress on Genetics, 1, 356-366 (1932) |
| [107] | Yao, A. C.-C., JACM, 50 1, 100-105 (2003) · Zbl 1326.68136 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
