Fast optimization algorithms and the cosmological constant

Denef and Douglas have observed that in certain landscape models the problem of finding small values of the cosmological constant is a large instance of a problem that is hard for the complexity class NP (Nondeterministic Polynomial-time). The number of elementary operations (quantum gates) needed to solve this problem by brute force search exceeds the estimated computational capacity of the observable Universe. Here we describe a way out of this puzzling circumstance: despite being NP-hard, the problem of finding a small cosmological constant can be attacked by more sophisticated algorithms whose performance vastly exceeds brute force search. In fact, in some parameter regimes the average-case complexity is polynomial. We demonstrate this by explicitly finding a cosmological constant of order ${10}^{-120}$ in a randomly generated $10^9$-dimensional Arkani-Hamed–Dimopoulos–Kachru landscape.

Figure 1

An example of the Karmarkar-Karp algorithm. At the first step the numbers are sorted. At each subsequent step, the largest two numbers are replaced by their difference, which is then inserted into the appropriate location in the list so that it remains sorted. The sequence of moves in the example shown finds the solution $1-(2-(4-(8-5)))=0$.

Figure 2

Expected relative optimal residue size versus input size for number partitioning problems on a block of $b$ random numbers with the specified distribution. For each block size $b$ in this given range, mean size for 1000 experiments is shown. Each experiment generated high precision floating point input data with mean one and a complete NPP solver produced the optimal residue. Assuming the distribution of optimal residues is exponential, the maximum likelihood estimator of the mean is biased; hence the least square error estimator was used to find the mean in each case. The model parameters with residue size $s=5.0b^{0.37}{2}^{-b}$ were generated by linear regression on the data with uniformly distributed inputs.

Figure 3

Plots of cumulative likelihood of observing the optimal residue versus (log) size of the optimal residue. The model is the cumulative distribution function of the exponential distribution where the single parameter $\lambda$ is computed from the data using the least squares estimator. For block sizes $b=10$, 20, 30, 40, each plot was generated from high precision floating point input data (uniformly or exponentially distributed) with mean one and a complete solver produced the optimal residue.

Figure 4

At each value of $n$, 200 instances of number partitioning are generated with each of the $n$ numbers independently sampled uniformly from $\{0,1,2,\dots ,2^{430}-1\}$. The fraction of instances in which the Karmarkar-Karp algorithm found a residue smaller than $2^{30}$ is shown for each $n$. The theoretically predicted success probability of $1-\exp [-\frac{e^{c\log (n{)}^2}}{2^{400}}]$ is also shown, with $c=0.6615$ determined by fitting to the data. The asymptotic value of $c$ as $n\to \infty$ is predicted to be $1/\sqrt{2}\simeq 0.7071$.

Figure 5

Plots of cumulative likelihood of observing the optimal residue versus (log) size of the optimal residue for a four-stage sieve. Input to stage 1 was $n=1.20\times {10}^6$ mean one uniformly distributed numbers. Stage 1 combined $b_1=20$ numbers in each number partitioning problem to produce 60000 optimal residues, forming the input to stage 2. Stage 2 combined $b_2=30$ numbers in each problem to produce 2000 optimal residues. Stage 3 combined $b_3=40$ numbers to produce 50 optimal residues. Finally stage 4 combined these $b_4=50$ numbers to produce an overall residue of $6.54\times {10}^{-38}$. This final residue was slightly smaller than the predicted $2^{-121.3}$. The sieve completed in 152 seconds on a standard desktop computer.