Finite-size scaling in random -satisfiability problems
arXiv:1005.0251 · doi:10.1103/PhysRevE.82.061109
Abstract
We provide a comprehensive view of various phase transitions in random -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 .
arXiv comment5 pages, 3 figures (6 eps files), 1 table; published version
References in corpus (18)
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Phase Transitions in the Coloring of Random Graphs
- A Landscape Analysis of Constraint Satisfaction Problems
- A variational description of the ground state structure in random satisfiability problems
- Finite-size scaling in complex networks
- Hiding solutions in random satisfiability problems: A statistical mechanics approach
- Focused Local Search for Random 3-Satisfiability
- Circumspect descent prevails in solving random constraint satisfaction problems
- Behavior of heuristics and state space structure near SAT/UNSAT transition
- Finite size scaling for the core of large random hypergraphs
- Relaxation and Metastability in the RandomWalkSAT search procedure
- Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
- Phase coexistence and finite-size scaling in random combinatorial problems
- On the critical exponents of random k-SAT
- Numerical Solution-Space Analysis of Satisfiability Problems
- Criticality and Universality in the Unit-Propagation Search Rule
- Constraint optimization and landscapes