1
|
Po HF, Yeung CH. Complete realization of energy landscapes and non-equilibrium trapping dynamics in small spin glass and optimization problems. Sci Rep 2024; 14:15675. [PMID: 38977813 PMCID: PMC11231248 DOI: 10.1038/s41598-024-65493-4] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/06/2023] [Accepted: 06/20/2024] [Indexed: 07/10/2024] Open
Abstract
Energy landscapes are high-dimensional surfaces underlie all physical systems, which determine crucially the energetic and behavioral dependence of the systems on variable configurations, but are difficult to be analyzed due to their high-dimensional nature. Here we introduce an approach to reveal for the complete energy landscapes of spin glasses and Boolean satisfiability problems with a small system size, and unravels their non-equilibrium dynamics at an arbitrary temperature for an arbitrarily long time. Remarkably, our results show that it can be less likely for the system to attain ground states when temperature decreases, due to trapping in individual local minima, which ceases at a different time, leading to multiple abrupt jumps in the ground-state probability. For large systems, we introduce a variant approach to extract partially the energy landscapes and observe both semi-analytically and in simulations similar phenomena. This work introduces new methodology to unravel the energy landscapes and non-equilibrium dynamics of glassy systems, and provides us with a clear, complete and new physical picture on their long-time behaviors inaccessible by existing approaches.
Collapse
Grants
- GRF 18304316 Research Grants Council of the Hong Kong Special Administrative Region, China
- GRF 18301217 Research Grants Council of the Hong Kong Special Administrative Region, China
- GRF 18301119 Research Grants Council of the Hong Kong Special Administrative Region, China
- GRF 18300623 Research Grants Council of the Hong Kong Special Administrative Region, China
- FLASS/DRF 04418 Dean's Research Fund of the Faculty of Liberal Arts and Social Sciences, The Education University of Hong Kong, Hong Kong Special Administrative Region, China
- FLASS/ROP 04396 Dean's Research Fund of the Faculty of Liberal Arts and Social Sciences, The Education University of Hong Kong, Hong Kong Special Administrative Region, China
- FLASS/DRF 04624 Dean's Research Fund of the Faculty of Liberal Arts and Social Sciences, The Education University of Hong Kong, Hong Kong Special Administrative Region, China
- RG67 2018-2019R R4015 Research Development Office Internal Research Grant, The Education University of Hong Kong, Hong Kong Special Administrative Region, China
- No. RG31 2020-2021R R4152 Research Development Office Internal Research Grant, The Education University of Hong Kong, Hong Kong Special Administrative Region, China
Collapse
Affiliation(s)
- Ho Fai Po
- Department of Science and Environmental Studies, The Education University of Hong Kong, 10 Lo Ping Road, Hong Kong, China
- Department of Mathematics, Aston University, Birmingham, B4 7ET, UK
| | - Chi Ho Yeung
- Department of Science and Environmental Studies, The Education University of Hong Kong, 10 Lo Ping Road, Hong Kong, China.
| |
Collapse
|
2
|
Catania G, Decelle A, Seoane B. Copycat perceptron: Smashing barriers through collective learning. Phys Rev E 2024; 109:065313. [PMID: 39020926 DOI: 10.1103/physreve.109.065313] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/12/2023] [Accepted: 06/03/2024] [Indexed: 07/20/2024]
Abstract
We characterize the equilibrium properties of a model of y coupled binary perceptrons in the teacher-student scenario, subject to a suitable cost function, with an explicit ferromagnetic coupling proportional to the Hamming distance between the students' weights. In contrast to recent works, we analyze a more general setting in which thermal noise is present that affects each student's generalization performance. In the nonzero temperature regime, we find that the coupling of replicas leads to a bend of the phase diagram towards smaller values of α: This suggests that the free entropy landscape gets smoother around the solution with perfect generalization (i.e., the teacher) at a fixed fraction of examples, allowing standard thermal updating algorithms such as Simulated Annealing to easily reach the teacher solution and avoid getting trapped in metastable states as happens in the unreplicated case, even in the computationally easy regime of the inference phase diagram. These results provide additional analytic and numerical evidence for the recently conjectured Bayes-optimal property of Replicated Simulated Annealing for a sufficient number of replicas. From a learning perspective, these results also suggest that multiple students working together (in this case reviewing the same data) are able to learn the same rule both significantly faster and with fewer examples, a property that could be exploited in the context of cooperative and federated learning.
Collapse
|
3
|
Primosch D, Zhang YH, Di Ventra M. Self-averaging of digital memcomputing machines. Phys Rev E 2023; 108:034306. [PMID: 37849117 DOI: 10.1103/physreve.108.034306] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/24/2022] [Accepted: 08/22/2023] [Indexed: 10/19/2023]
Abstract
Digital memcomputing machines (DMMs) are a new class of computing machines that employ nonquantum dynamical systems with memory to solve combinatorial optimization problems. Here, we show that the time to solution (TTS) of DMMs follows an inverse Gaussian distribution, with the TTS self-averaging with increasing problem size, irrespective of the problem they solve. We provide both an analytical understanding of this phenomenon and numerical evidence by solving instances of the 3-SAT (satisfiability) problem. The self-averaging property of DMMs with problem size implies that they are increasingly insensitive to the detailed features of the instances they solve. This is in sharp contrast to traditional algorithms applied to the same problems, illustrating another advantage of this physics-based approach to computation.
Collapse
Affiliation(s)
- Daniel Primosch
- Department of Physics, University of California San Diego, La Jolla, California 92093, USA
| | - Yuan-Hang Zhang
- Department of Physics, University of California San Diego, La Jolla, California 92093, USA
| | - Massimiliano Di Ventra
- Department of Physics, University of California San Diego, La Jolla, California 92093, USA
| |
Collapse
|
4
|
Fu H, Xu Y, Wu G, Liu J, Chen S, He X. Emphasis on the flipping variable: Towards effective local search for hard random satisfiability. Inf Sci (N Y) 2021. [DOI: 10.1016/j.ins.2021.03.009] [Citation(s) in RCA: 4] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/30/2022]
|
5
|
Zhang YH, Di Ventra M. Directed percolation and numerical stability of simulations of digital memcomputing machines. CHAOS (WOODBURY, N.Y.) 2021; 31:063127. [PMID: 34241305 DOI: 10.1063/5.0045375] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 01/26/2021] [Accepted: 06/01/2021] [Indexed: 06/13/2023]
Abstract
Digital memcomputing machines (DMMs) are a novel, non-Turing class of machines designed to solve combinatorial optimization problems. They can be physically realized with continuous-time, non-quantum dynamical systems with memory (time non-locality), whose ordinary differential equations (ODEs) can be numerically integrated on modern computers. Solutions of many hard problems have been reported by numerically integrating the ODEs of DMMs, showing substantial advantages over state-of-the-art solvers. To investigate the reasons behind the robustness and effectiveness of this method, we employ three explicit integration schemes (forward Euler, trapezoid, and Runge-Kutta fourth order) with a constant time step to solve 3-SAT instances with planted solutions. We show that (i) even if most of the trajectories in the phase space are destroyed by numerical noise, the solution can still be achieved; (ii) the forward Euler method, although having the largest numerical error, solves the instances in the least amount of function evaluations; and (iii) when increasing the integration time step, the system undergoes a "solvable-unsolvable transition" at a critical threshold, which needs to decay at most as a power law with the problem size, to control the numerical errors. To explain these results, we model the dynamical behavior of DMMs as directed percolation of the state trajectory in the phase space in the presence of noise. This viewpoint clarifies the reasons behind their numerical robustness and provides an analytical understanding of the solvable-unsolvable transition. These results land further support to the usefulness of DMMs in the solution of hard combinatorial optimization problems.
Collapse
Affiliation(s)
- Yuan-Hang Zhang
- Department of Physics, University of California, San Diego, California 92093, USA
| | | |
Collapse
|
6
|
|
7
|
Bearden SRB, Pei YR, Di Ventra M. Efficient solution of Boolean satisfiability problems with digital memcomputing. Sci Rep 2020; 10:19741. [PMID: 33184386 PMCID: PMC7665037 DOI: 10.1038/s41598-020-76666-2] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/28/2020] [Accepted: 10/29/2020] [Indexed: 11/25/2022] Open
Abstract
Boolean satisfiability is a propositional logic problem of interest in multiple fields, e.g., physics, mathematics, and computer science. Beyond a field of research, instances of the SAT problem, as it is known, require efficient solution methods in a variety of applications. It is the decision problem of determining whether a Boolean formula has a satisfying assignment, believed to require exponentially growing time for an algorithm to solve for the worst-case instances. Yet, the efficient solution of many classes of Boolean formulae eludes even the most successful algorithms, not only for the worst-case scenarios, but also for typical-case instances. Here, we introduce a memory-assisted physical system (a digital memcomputing machine) that, when its non-linear ordinary differential equations are integrated numerically, shows evidence for polynomially-bounded scalability while solving "hard" planted-solution instances of SAT, known to require exponential time to solve in the typical case for both complete and incomplete algorithms. Furthermore, we analytically demonstrate that the physical system can efficiently solve the SAT problem in continuous time, without the need to introduce chaos or an exponentially growing energy. The efficiency of the simulations is related to the collective dynamical properties of the original physical system that persist in the numerical integration to robustly guide the solution search even in the presence of numerical errors. We anticipate our results to broaden research directions in physics-inspired computing paradigms ranging from theory to application, from simulation to hardware implementation.
Collapse
Affiliation(s)
- Sean R B Bearden
- Department of Physics, University of California, San Diego, La Jolla, CA, 92093, USA
| | - Yan Ru Pei
- Department of Physics, University of California, San Diego, La Jolla, CA, 92093, USA
| | | |
Collapse
|
8
|
Hamze F, Raymond J, Pattison CA, Biswas K, Katzgraber HG. Wishart planted ensemble: A tunably rugged pairwise Ising model with a first-order phase transition. Phys Rev E 2020; 101:052102. [PMID: 32575320 DOI: 10.1103/physreve.101.052102] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/01/2019] [Accepted: 03/31/2020] [Indexed: 11/07/2022]
Abstract
We propose the Wishart planted ensemble, a class of zero-field Ising models with tunable algorithmic hardness and specifiable (or planted) ground state. The problem class arises from a simple procedure for generating a family of random integer programming problems with specific statistical symmetry properties but turns out to have intimate connections to a sign-inverted variant of the Hopfield model. The Hamiltonian contains only 2-spin interactions, with the coupler matrix following a type of Wishart distribution. The class exhibits a classical first-order phase transition in temperature. For some parameter settings the model has a locally stable paramagnetic state, a feature which correlates strongly with difficulty in finding the ground state and suggests an extremely rugged energy landscape. We analytically probe the ensemble thermodynamic properties by deriving the Thouless-Anderson-Palmer equations and free energy and corroborate the results with a replica and annealed approximation analysis; extensive Monte Carlo simulations confirm our predictions of the first-order transition temperature. The class exhibits a wide variation in algorithmic hardness as a generation parameter is varied, with a pronounced easy-hard-easy profile and peak in solution time towering many orders of magnitude over that of the easy regimes. By deriving the ensemble-averaged energy distribution and taking into account finite-precision representation, we propose an analytical expression for the location of the hardness peak and show that at fixed precision, the number of constraints in the integer program must increase with system size to yield truly hard problems. The Wishart planted ensemble is interesting for its peculiar physical properties and provides a useful and analytically transparent set of problems for benchmarking optimization algorithms.
Collapse
Affiliation(s)
- Firas Hamze
- Microsoft Quantum, Microsoft, Redmond, Washington 98052, USA.,D-Wave Systems, Inc., Burnaby, British Columbia, Canada V5G 4M9
| | - Jack Raymond
- D-Wave Systems, Inc., Burnaby, British Columbia, Canada V5G 4M9
| | - Christopher A Pattison
- Department of Physics, California Institute of Technology, Pasadena, California 91125, USA.,Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Katja Biswas
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Helmut G Katzgraber
- Microsoft Quantum, Microsoft, Redmond, Washington 98052, USA.,Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA.,Santa Fe Institute, Santa Fe, New Mexico 87501, USA
| |
Collapse
|
9
|
Perera D, Hamze F, Raymond J, Weigel M, Katzgraber HG. Computational hardness of spin-glass problems with tile-planted solutions. Phys Rev E 2020; 101:023316. [PMID: 32168655 DOI: 10.1103/physreve.101.023316] [Citation(s) in RCA: 6] [Impact Index Per Article: 1.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/24/2019] [Accepted: 02/05/2020] [Indexed: 12/14/2022]
Abstract
We investigate the computational hardness of spin-glass instances on a square lattice, generated via a recently introduced tunable and scalable approach for planting solutions. The method relies on partitioning the problem graph into edge-disjoint subgraphs and planting frustrated, elementary subproblems that share a common local ground state, which guarantees that the ground state of the entire problem is known a priori. Using population annealing Monte Carlo, we compare the typical hardness of problem classes over a large region of the multidimensional tuning parameter space. Our results show that the problems have a wide range of tunable hardness. Moreover, we observe multiple transitions in the hardness phase space, which we further corroborate using simulated annealing and simulated quantum annealing. By investigating thermodynamic properties of these planted systems, we demonstrate that the harder samples undergo magnetic ordering transitions which are also ultimately responsible for the observed hardness transitions on changing the sample composition.
Collapse
Affiliation(s)
- Dilina Perera
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Firas Hamze
- D-Wave Systems, Inc., 3033 Beta Avenue, Burnaby, British Columbia, Canada V5G 4M9
| | - Jack Raymond
- D-Wave Systems, Inc., 3033 Beta Avenue, Burnaby, British Columbia, Canada V5G 4M9
| | - Martin Weigel
- Centre for Fluid and Complex Systems, Coventry University, Coventry, CV1 5FB, England
| | - Helmut G Katzgraber
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA.,Microsoft Quantum, Microsoft, Redmond, Washington 98052, USA.,Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA
| |
Collapse
|
10
|
Ricci-Tersenghi F, Semerjian G, Zdeborová L. Typology of phase transitions in Bayesian inference problems. Phys Rev E 2019; 99:042109. [PMID: 31108676 DOI: 10.1103/physreve.99.042109] [Citation(s) in RCA: 17] [Impact Index Per Article: 3.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/16/2018] [Indexed: 11/07/2022]
Abstract
Many inference problems undergo phase transitions as a function of the signal-to-noise ratio, a prominent example of this phenomenon being found in the stochastic block model (SBM) that generates a random graph with a hidden community structure. Some of these phase transitions affect the information-theoretic optimal (but possibly computationally expensive) estimation procedure, others concern the behavior of efficient iterative algorithms. A computational gap opens when the phase transitions for these two aspects do not coincide, leading to a hard phase in which optimal inference is computationally challenging. In this paper we refine this description in two ways. From a qualitative perspective, we emphasize the existence of more generic phase diagrams with a hybrid-hard phase, in which it is computationally easy to reach a nontrivial inference accuracy but computationally hard to match the information-theoretic optimal one. We support this discussion by quantitative expansions of the functional cavity equations that describe inference problems on sparse graphs, around their trivial solution. These expansions shed light on the existence of hybrid-hard phases, for a large class of planted constraint satisfaction problems, and on the question of the tightness of the Kesten-Stigum (KS) bound for the associated tree reconstruction problem. Our results show that the instability of the trivial fixed point is not generic evidence for the Bayes optimality of the message-passing algorithms. We clarify in particular the status of the symmetric SBM with four communities and of the tree reconstruction of the associated Potts model: In the assortative (ferromagnetic) case the KS bound is always tight, whereas in the disassortative (antiferromagnetic) case we exhibit an explicit criterion involving the degree distribution that separates a large-degree regime where the KS bound is tight and a low-degree regime where it is not. We also investigate the SBM with two communities of different sizes, also known as the asymmetric Ising model, and describe quantitatively its computational gap as a function of its asymmetry, as well as a version of the SBM with two groups of q_{1} and q_{2} communities. We complement this study with numerical simulations of the belief propagation iterative algorithm, confirming that its behavior on large samples is well described by the cavity method.
Collapse
Affiliation(s)
- Federico Ricci-Tersenghi
- Diparimento di Fisica, Sapienza Università di Roma, Nanotec CNR, UOS di Roma, and INFN Sezione di Roma 1, Piazzale Aldo Moro 5, 00185 Roma, Italy
| | - Guilhem Semerjian
- Laboratoire de Physique, Ecole Normale Supérieure, Université PSL, CNRS, Sorbonne Université, Université Paris-Diderot, Université Sorbonne Paris Cité, Paris, France
| | - Lenka Zdeborová
- Institut de Physique Théorique, CNRS, CEA, Université Paris-Saclay, Gif-sur-Yvette, France
| |
Collapse
|
11
|
Luo W, Liu R, Jiang H, Zhao D, Wu L. Three Branches of Negative Representation of Information: A Survey. IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE 2018. [DOI: 10.1109/tetci.2018.2829907] [Citation(s) in RCA: 19] [Impact Index Per Article: 3.2] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/08/2022]
|
12
|
Hamze F, Jacob DC, Ochoa AJ, Perera D, Wang W, Katzgraber HG. From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems. Phys Rev E 2018; 97:043303. [PMID: 29758754 DOI: 10.1103/physreve.97.043303] [Citation(s) in RCA: 11] [Impact Index Per Article: 1.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/24/2017] [Indexed: 11/07/2022]
Abstract
We present a methodology for generating Ising Hamiltonians of tunable complexity and with a priori known ground states based on a decomposition of the model graph into edge-disjoint subgraphs. The idea is illustrated with a spin-glass model defined on a cubic lattice, where subproblems, whose couplers are restricted to the two values {-1,+1}, are specified on unit cubes and are parametrized by their local degeneracy. The construction is shown to be equivalent to a type of three-dimensional constraint-satisfaction problem known as the tiling puzzle. By varying the proportions of subproblem types, the Hamiltonian can span a dramatic range of typical computational complexity, from fairly easy to many orders of magnitude more difficult than prototypical bimodal and Gaussian spin glasses in three space dimensions. We corroborate this behavior via experiments with different algorithms and discuss generalizations and extensions to different types of graphs.
Collapse
Affiliation(s)
- Firas Hamze
- D-Wave Systems, Inc., 3033 Beta Avenue, Burnaby, British Columbia, Canada V5G 4M9
| | - Darryl C Jacob
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Andrew J Ochoa
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Dilina Perera
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Wenlong Wang
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Helmut G Katzgraber
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA.,1QB Information Technologies, Vancouver, British Columbia, Canada V6B 4W4.,Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA
| |
Collapse
|
13
|
Zhang BH, Wagenbreth G, Martin-Mayor V, Hen I. Advantages of Unfair Quantum Ground-State Sampling. Sci Rep 2017; 7:1044. [PMID: 28432287 PMCID: PMC5430793 DOI: 10.1038/s41598-017-01096-6] [Citation(s) in RCA: 12] [Impact Index Per Article: 1.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/26/2017] [Accepted: 03/21/2017] [Indexed: 11/28/2022] Open
Abstract
The debate around the potential superiority of quantum annealers over their classical counterparts has been ongoing since the inception of the field. Recent technological breakthroughs, which have led to the manufacture of experimental prototypes of quantum annealing optimizers with sizes approaching the practical regime, have reignited this discussion. However, the demonstration of quantum annealing speedups remains to this day an elusive albeit coveted goal. We examine the power of quantum annealers to provide a different type of quantum enhancement of practical relevance, namely, their ability to serve as useful samplers from the ground-state manifolds of combinatorial optimization problems. We study, both numerically by simulating stoquastic and non-stoquastic quantum annealing processes, and experimentally, using a prototypical quantum annealing processor, the ability of quantum annealers to sample the ground-states of spin glasses differently than thermal samplers. We demonstrate that (i) quantum annealers sample the ground-state manifolds of spin glasses very differently than thermal optimizers (ii) the nature of the quantum fluctuations driving the annealing process has a decisive effect on the final distribution, and (iii) the experimental quantum annealer samples ground-state manifolds significantly differently than thermal and ideal quantum annealers. We illustrate how quantum annealers may serve as powerful tools when complementing standard sampling algorithms.
Collapse
Affiliation(s)
| | | | - Victor Martin-Mayor
- Departamento de Física Teórica I, Universidad Complutense, 28040, Madrid, Spain.,Instituto de Biocomputación y Física de Sistemas Complejos (BIFI), Zaragoza, Spain
| | - Itay Hen
- Information Sciences Institute, University of Southern California, Marina del Rey, California, 90292, USA. .,Department of Physics and Astronomy and Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, California, 90089, USA.
| |
Collapse
|
14
|
|
15
|
|
16
|
|
17
|
Lee SH, Ha M, Jeon C, Jeong H. Finite-size scaling in random K-satisfiability problems. Phys Rev E 2011; 82:061109. [PMID: 21230646 DOI: 10.1103/physreve.82.061109] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/03/2010] [Revised: 10/28/2010] [Indexed: 11/07/2022]
Abstract
We provide a comprehensive view of various phase transitions in random K-satisfiability problems solved by stochastic-local-search algorithms. In particular, we focus on the finite-size scaling (FSS) exponent, which is mathematically important and practically useful in analyzing finite systems. Using the FSS theory of nonequilibrium absorbing phase transitions, we show that the density of unsatisfied clauses clearly indicates the transition from the solvable (absorbing) phase to the unsolvable (active) phase as varying the noise parameter and the density of constraints. Based on the solution clustering (percolation-type) argument, we conjecture two possible values of the FSS exponent, which are confirmed reasonably well in numerical simulations for 2 ≤ K ≤ 3.
Collapse
Affiliation(s)
- Sang Hoon Lee
- Department of Physics, Korea Advanced Institute of Science and Technology, Daejeon 305-701, Korea
| | | | | | | |
Collapse
|
18
|
|
19
|
Krzakala F, Zdeborová L. Hiding quiet solutions in random constraint satisfaction problems. PHYSICAL REVIEW LETTERS 2009; 102:238701. [PMID: 19658978 DOI: 10.1103/physrevlett.102.238701] [Citation(s) in RCA: 20] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 01/16/2009] [Revised: 04/14/2009] [Indexed: 05/28/2023]
Abstract
We study constraint satisfaction problems on the so-called planted random ensemble. We show that for a certain class of problems, e.g., graph coloring, many of the properties of the usual random ensemble are quantitatively identical in the planted random ensemble. We study the structural phase transitions and the easy-hard-easy pattern in the average computational complexity. We also discuss the finite temperature phase diagram, finding a close connection with the liquid-glass-solid phenomenology.
Collapse
|
20
|
Li K, Ma H, Zhou H. From one solution of a 3-satisfiability formula to a solution cluster: frozen variables and entropy. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2009; 79:031102. [PMID: 19391897 DOI: 10.1103/physreve.79.031102] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 10/29/2008] [Indexed: 05/27/2023]
Abstract
A solution to a 3-satisfiability (3-SAT) formula can be expanded into a cluster, all other solutions of which are reachable from this one through a sequence of single-spin flips. Some variables in the solution cluster are frozen to the same spin values by one of two different mechanisms: frozen-core formation and long-range frustrations. While frozen cores are identified by a local whitening algorithm, long-range frustrations are very difficult to trace, and they make an entropic belief-propagation (BP) algorithm fail to converge. For the BP algorithm to reach a fixed point, the spin values of a tiny fraction of variables (chosen according to the whitening algorithm) are externally fixed during the iteration. From the calculated entropy values, we infer that, for a large random 3-SAT formula with constraint density close to the satisfiability threshold, the solutions obtained by the survey-propagation or WALKSAT algorithms belong neither to the most dominating clusters of the formula nor to the most abundant clusters. This work indicates that a single-solution cluster of a random 3-SAT formula may have further community structures.
Collapse
Affiliation(s)
- Kang Li
- Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China
| | | | | |
Collapse
|
21
|
|
22
|
Jia H, Moore C, Selman B. From Spin Glasses to Hard Satisfiable Formulas. THEORY AND APPLICATIONS OF SATISFIABILITY TESTING 2005. [DOI: 10.1007/11527695_16] [Citation(s) in RCA: 6] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 12/12/2022]
|
23
|
van Mourik J, Saad D. Random graph coloring: statistical physics approach. PHYSICAL REVIEW E 2002; 66:056120. [PMID: 12513569 DOI: 10.1103/physreve.66.056120] [Citation(s) in RCA: 30] [Impact Index Per Article: 1.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 07/18/2002] [Indexed: 11/07/2022]
Abstract
The problem of vertex coloring in random graphs is studied using methods of statistical physics and probability. Our analytical results are compared to those obtained by exact enumeration and Monte Carlo simulations. We critically discuss the merits and shortcomings of the various methods, and interpret the results obtained. We present an exact analytical expression for the two-coloring problem as well as general replica symmetric approximated solutions for the thermodynamics of the graph coloring problem with p colors and K-body edges.
Collapse
Affiliation(s)
- J van Mourik
- The Neural Computing Research Group, Aston University, Birmingham B4 7ET, United Kingdom
| | | |
Collapse
|