Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExhaustive enumeration unveils clustering and freezing in random 3-SAT
112
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study geometrical properties of the complete set of solutions of the random 3-satisfiability problem. We show that even for moderate system sizes the number of clusters corresponds surprisingly well with the theoretic asymptotic prediction. We locate the freezing transition in the space of solutions which has been conjectured to be relevant in explaining the onset of computational hardness in random constraint satisfaction problems.
rate research
Read More
The set of solutions of random constraint satisfaction problems (zero energy groundstates of mean-field diluted spin glasses) undergoes several structural phase transitions as the amount of constraints is increased. This set first breaks down into a large number of well separated clusters. At the freezing transition, which is in general distinct from the clustering one, some variables (spins) take the same value in all solutions of a given cluster. In this paper we study the critical behavior around the freezing transition, which appears in the unfrozen phase as the divergence of the sizes of the rearrangements induced in response to the modification of a variable. The formalism is developed on generic constraint satisfaction problems and applied in particular to the random satisfiability of boolean formulas and to the coloring of random graphs. The computation is first performed in random tree ensembles, for which we underline a connection with percolation models and with the reconstruction problem of information theory. The validity of these results for the original random ensembles is then discussed in the framework of the cavity method.
The effects of bond randomness on the universality aspects of the simple cubic lattice ferromagnetic Blume-Capel model are discussed. The system is studied numerically in both its first- and second-order phase transition regimes by a comprehensive finite-size scaling analysis. We find that our data for the second-order phase transition, emerging under random bonds from the second-order regime of the pure model, are compatible with the universality class of the 3d random Ising model. Furthermore, we find evidence that, the second-order transition emerging under bond randomness from the first-order regime of the pure model, belongs to a new and distinctive universality class. The first finding reinforces the scenario of a single universality class for the 3d Ising model with the three well-known types of quenched uncorrelated disorder (bond randomness, site- and bond-dilution). The second, amounts to a strong violation of universality principle of critical phenomena. For this case of the ex-first-order 3d Blume-Capel model, we find sharp differences from the critical behaviors, emerging under randomness, in the cases of the ex-first-order transitions of the corresponding weak and strong first-order transitions in the 3d three-state and four-state Potts models.
Optimization is fundamental in many areas of science, from computer science and information theory to engineering and statistical physics, as well as to biology or social sciences. It typically involves a large number of variables and a cost function depending on these variables. Optimization problems in the NP-complete class are particularly difficult, it is believed that the number of operations required to minimize the cost function is in the most difficult cases exponential in the system size. However, even in an NP-complete problem the practically arising instances might, in fact, be easy to solve. The principal question we address in this thesis is: How to recognize if an NP-complete constraint satisfaction problem is typically hard and what are the main reasons for this? We adopt approaches from the statistical physics of disordered systems, in particular the cavity method developed originally to describe glassy systems. We describe new properties of the space of solutions in two of the most studied constraint satisfaction problems - random satisfiability and random graph coloring. We suggest a relation between the existence of the so-called frozen variables and the algorithmic hardness of a problem. Based on these insights, we introduce a new class of problems which we named locked constraint satisfaction, where the statistical description is easily solvable, but from the algorithmic point of view they are even more challenging than the canonical satisfiability.
We introduce and study the random locked constraint satisfaction problems. When increasing the density of constraints, they display a broad clustered phase in which the space of solutions is divided into many isolated points. While the phase diagram can be found easily, these problems, in their clustered phase, are extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions. We thus propose new benchmarks of really hard optimization problems and provide insight into the origin of their typical hardness.
Mappings of classical computation onto statistical mechanics models have led to remarkable successes in addressing some complex computational problems. However, such mappings display thermodynamic phase transitions that may prevent reaching solution even for easy problems known to be solvable in polynomial time. Here we map universal reversible classical computations onto a planar vertex model that exhibits no bulk classical thermodynamic phase transition, independent of the computational circuit. Within our approach the solution of the computation is encoded in the ground state of the vertex model and its complexity is reflected in the dynamics of the relaxation of the system to its ground state. We use thermal annealing with and without learning to explore typical computational problems. We also construct a mapping of the vertex model into the Chimera architecture of the D-Wave machine, initiating an approach to reversible classical computation based on state-of-the-art implementations of quantum annealing.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
