Computational Hardness of Random CNP Instances

Table of Links

I. Introduction

II. Spim Performance, Advantages and Generality

III. Inherently Low Rank Problems

A. Properties of Low Rank Graphs

B. Weakly NP-Complete Problems and Hardware Precision Limitation

C. Limitation of Low Rank Matrix Mapping

IV. Low Rank Approximation

A. Decomposition of Target Coupling Matrix

B. How Fields Influence Ran

C. Low Rank Approximation of Coupling Matrices

D. Low-Rank Approximation of Random Coupling Matrices

E. Low Rank Approximation for Portfolio Optimization

F. Low-Rank Matrices in Restricted Boltzmann Machines

V. Constrained Number Partitioning Problem

A. Definition and Characteristics of the Constrained Number Partitioning Problem

B. Computational Hardness of Random CNP Instances

VI. Translation Invariant Problems

A. “Realistic” Spin Glass

B. Circulant Graphs

VII. Conclusions, Acknowledgements, and References

B. Computational Hardness of Random CNP Instances

As the number of integers N in a CNP problem increases, the probability of finding a perfect partition will undergo a phase transition from 0 to 1, but the critical value of Nc where this happens is expected to increase as bias S of the problem increases because it is increasingly challenging to balance the sums in each subset while fulfilling the constraint of greater cardinality difference. This trend is observed in Fig. 3(a). A complete picture of the phase transition landscape is shown in Fig. 3(b), which is the probability of the existence of a perfect solution in a random CNP problem with various numbers of integers N and bias S. We can observe a “hard” phase in which the probability of a perfect solution’s existence is low (labelled as region 2 in the colour map) and a “perfect” phase in which the probability of a perfect solution’s existence is close to 1 (labelled as region 3). It can be observed that the phase transition between the “hard” and “perfect” phases is not sharp, and there exists an intermediate region where the probability of a perfect solution being present is neither close to 0 nor 1. This can be attributed to the finite system size N. Unlike the theoretical studies presented in [60], which depicts the asymptotic behaviour when N → ∞, this phase diagram models a finite system implementable in SPIM hardware. From the phase diagram, we observe that region 2, where the probability of a perfect solution’s existence is close to 0, extends into N values much greater than L = 12 used in the simulation. Hence, this numerical experiment suggests that it is possible to realize CNP problem instances with size N much greater than hardware precision L on SPIM and still keep the parameters in region 2, where the probability of a perfect solution being present is very low.

Next, we must understand if problem instances in region 2 represent computationally hard instances. The existing state-of-the-art pseudo-polynomial time algorithm for number partitioning problems is the complete differencing algorithm [38]. As shown in Fig. 4, the algorithm performs the search in a depth-first manner through a tree. The root comprises all integers in a descending order. At each node with more than one element, the node leads to new branches. The left branch takes the difference of the first two elements of the parent node, denoting the decision to assign the two leading elements into two different subsets. The right branch takes the sum of the first two elements of the parent node, denoting the decision to assign the two leading elements to the same subset. The only integer in each leaf node indicates the final discrepancy corresponding to the partition defined by the route from the root to the leaf.

Here, we investigate two versions of the CNP problem. The first is a decision problem: given a CNP instance, determine if a perfect solution exists. The complete differencing algorithm was adapted by enforcing the bias constraint and then used on many random CNP problem instances with given size N and bias S. The number of possible configurations that must be searched before the determination can be made is shown in Fig. 5(a). It can be observed that the number of searched configurations first increases exponentially with N before hitting a peak. We note that the average hardness of problems, as indicated by the number of configurations searched, peaks at around the same time as the phase transition from the "hard" phase to the "perfect" phase shown in Fig. 3(a). This is because if a perfect solution exists, the algorithm can locate it early on without searching the entire configuration space. If no perfect solution exists, the algorithm will likely have to search most part of the configuration space to rule it out. Hence, our numerical test shows that CNP and NPP are likely to behave similarly, with the existence of a perfect solution correlated with the problem being easy.

The second version of CNP problems we investigate is a harder optimization problem: given a CNP instance, find the best partition, regardless of whether it is perfect. Figure 5(b) shows the degenerate ground states in randomly generated CNP problem instances with different bias parameters b = S/N but with fixed precision L = 12. When N is smaller than L, it can be observed that the number of degenerate ground states did not grow exponentially with N for all values of bias ratio parameters b, which corresponds to the lower-left corner of region 2 in Fig. 3(b). When N is larger than L, the number of degenerate ground states grows exponentially with N for smaller values of b. For the largest considered b value of 0.4, the number of degenerate ground states is approximately constant by an order of magnitude, even as the total solution space grows exponentially with N. This strongly suggests that for the largest bias ratio b value, the problem remains computationally hard even as N grows while the precision L is fixed. Hence, random CNP problems with large bias ratio values can be meaningful benchmark problems for testing the performance of SPIM hardware in solving computationally hard problems because they have limited precision requirements and can be mapped to an Ising problem with a low-rank coupling matrix, as we show in the following subsection.