Random subcube model

In statistical mechanics, the random-subcube model (RSM) is an exactly solvable model that reproduces key properties of hard constraint satisfaction problems (CSPs) and optimization problems, such as geometrical organization of solutions, the effects of frozen variables, and the limitations of various algorithms like decimation schemes.

The RSM consists of a set of N binary variables, where solutions are defined as points in a hypercube.

The model introduces clusters, which are random subcubes of the hypercube, representing groups of solutions sharing specific characteristics.

As the density of constraints increases, the solution space undergoes a series of phase transitions similar to those observed in CSPs like random k-satisfiability (k-SAT) and random k-coloring (k-COL).

These transitions include clustering, condensation, and ultimately the unsatisfiable phase where no solutions exist.

The RSM is equivalent to these real CSPs in the limit of large constraint size.

Notably, it reproduces the cluster size distribution and freezing properties of k-SAT and k-COL in the large-k limit.

This is similar to how the random energy model is the large-p limit of the p-spin glass model.

Only those satisfying the constraints are allowed.

Each random subcube model is defined by two parameters

The entropy density of the system in bits is

be the number of clusters with entropy density

{\displaystyle {\begin{aligned}P&:={\binom {N}{sN}}p^{(1-s)N}(1-p)^{sN},\\\Sigma (s)&:=1-\alpha -D_{KL}(s\|1-p)\\D_{KL}(s\|1-p)&:=s\log _{2}{\frac {s}{1-p}}+(1-s)\log _{2}{\frac {1-s}{p}}\end{aligned}}}

by the law of small numbers.

For each state, the number of clusters it is in is also binomially distributed, with expectation

, and so each state is in an exponential number of clusters.

Indeed, in that case, the probability that all states are allowed is

Thus almost surely, all states are allowed, and the entropy density is 1 bit per particle.

, then it concentrates to zero exponentially, and so most states are not in any cluster.

The state space is thus roughly speaking the disjoint union of the clusters.

, therefore, the state space is dominated by clusters with optimal entropy density

Thus, in the clustered phase, the state space is almost entirely partitioned among

Roughly, the state space looks like exponentially many equally-sized clusters.

Another phase transition occurs when

, the optimal entropy density becomes unreachable, as there almost surely exists zero clusters with entropy density

Instead, the state space is dominated by clusters with entropy close to

, the contribution of clusters with entropy density

of the total state space is covered by only a finite number of clusters.

The state space looks partitioned into clusters with exponentially decaying sizes.

The RSM can be extended to include energy landscapes, allowing for the study of glassy behavior, temperature chaos, and the dynamic transition.