The SAT phase transition
1373490
The SAT Phase Transition
We describe a detailed experimental investigation of the phase transition for several different classes of randomly generated satisfiability problems. We observe a remarkable consistency of fea tures in the phase transition despite the presence in some of the problem classes of clauses of mixed lengths. For instance, each of the problem classes considered has a sharp transition from satisfiable to unsatisfiable problems at a critical value. In addition, there is a com mon easy hard easy pattern in the median difficulty of the problems, with the hardest problems being associated with the phase transition. However, the difficulty of problems of mixed clause lengths is much more variable than that of fixed clause length. Indeed, whilst the me dian difficulty of random problems of mixed clause lengths can be orders of magnitude easier than that of equivalently sized problems of fixed clause length, the hardest problems of mixed clause lengths can be orders of magnitude harder than the hardest equivalently sized problems of fixed clause length. Such very hard random problems may be of considerable practical and theoretical use in analysing algorithm performance.
ECAI
Ian P Gent Toby Walsh
934891
The SAT phase transition
Phase transition is an important feature of SAT problem. For randomk SAT model, it is proved that asr (ratio of clauses to variables) increases, the structure of solutions will undergo a sudden change like satisfiability phase transition whenr reaches a threshold point (r=rs) This phenomenon shows that the satisfying truth assignments suddenly shift from being relatively different from each other to being very similar to each other.
ArXiv
Ke Xu Wei Li
692513
Observed Lower Bounds for Random 3 SAT Phase Transition Density Using Linear Programming
We introduce two incomplete polynomial time algorithms to solve satisfiability problems which both use Linear Programming (LP) techniques. First, the FlipFlop LP attempts to simulate a Quadratic Program which would solve the CNF at hand. Second, the WeightedLinearAutarky LP is an extended variant of the LinearAutarky LP as defined by Kullmann [6] and iteratively updates its weights to find autarkies in a given formula. Besides solving satisfiability problems, this LP could also be used to study the existence of autark assignments in formulas. Results within the experimental domain (up to 1000 variables) show a considerably sharper lower bound for the uniform random 3 Sat phase transition density than the proved lower bound of the myopic algorithm 3.26) by Achlioptas [1] and even than that of the greedy algorithm 3.52) proposed by Kaporis [5]
SAT
Marijn J H Heule Hans van Maaren
93001708
On the Empirical Time Complexity of Scale Free 3 SAT at the Phase Transition
The hardness of formulas at the solubility phase transition of random propositional satisfiability (SAT) has been intensely studied for decades both empirically and theoretically. Solvers based on stochastic local search (SLS) appear to scale very well at the critical threshold, while complete backtracking solvers exhibit exponential scaling. On industrial SAT instances, this phenomenon is inverted: backtracking solvers can tackle large industrial problems, where SLS based solvers appear to stall. Industrial instances exhibit sharply different structure than uniform random instances. Among many other properties, they are often heterogeneous in the sense that some variables appear in many while others appear in only few clauses.
TACAS
Thomas Blasius Tobias Friedrich Andrew M Sutton
207957046
Phase Transition in Realistic Random SAT Models
Phase transition in random SAT formulas is one of the properties best studied by theoretical SAT researchers. There exists a constant rk depending on k such that, if we choose randomly a k SAT formula over n variables and m clauses, it will be satisfiable with high probability, if m/n r, and unsatisfiable, otherwise. However, this criterion is useless in practice, because real world or industrial instances have some properties not shown in random formulas. In the last years, several models of realistic random formulas have been proposed. Here we discuss about the phase transition in these models, and about the size of unsatisfiability proofs. We observe that in these models, like in real world formulas, there is not a sharp phase transition, the transition occurs for smaller values of r, and the proofs on unsatisfiable formulas are smaller than in the classical random model. We also discuss about the strategies used by modern SAT solvers to exploit these properties.
CCIA
Carlos Ansotegui Maria Luisa Bonet Jordi Levy
6023211
Percolation and Phase Transition in SAT
Erd\"os and R\'enyi proved in 1960 that a drastic change occurs in a large random graph when the number of edges is half the number of nodes: a giant connected component surges. This was the origin of percolation theory, where statistic mechanics and mean field techniques are applied to study the behavior of graphs and other structures when we remove edges randomly. In the 90's the study of random SAT instances started. It was proved that in large 2 SAT random instances also a drastic change occurs when the number of clauses is equal to the number of variables: the formula almost surely changes from satisfiable to unsatisfiable. The same effect, but at distinct clause/variable ratios, was detected in k SAT and other random models. In this paper we study the relation between both phenomena, and establish a condition that allows us to easily find the phase transition threshold in several models of 2 SAT formulas. In particular, we prove the existence of a phase transition threshold in scale free random 2 SAT formulas.
ArXiv
Jordi Levy
67371408
A new hybridized algorithm based on Population Based Simulated Annealing with an experimental study of phase transition in 3 SAT
Abstract This paper is about experiments for satisfiability problem using a new algorithm (GR MM PBSA) that improves the algorithm Population Based Simulated Annealing (PBSA) GR MM PBSA runs in a parallel way Simulated Annealing (SA) and Threshold Annealing (TA) algorithms with a Golden Ratio space search strategy and Markovian Model to select initial and final temperature. In this paper we execute differents hybridized Simulated Annealing (or Threshold Accepting) algorithms and compares the efficiency of these, using a metric based on transition phase effect. Simulated Annealing Algorithms (SAA) theoretically can reach the optimum if the control parameters and cooling scheme are chosen correctly. All algorithms are compared with a metric based on transition phase obtained for 3 SAT instances. This paper shows the results of SAA hybridizations are more efficient than the original algorithm, without increasing their computational complexity. We also show the experimental data about runs with 820 3 SAT instances with ratio clauses variables between 2.0 to 6.0.
ICCSCI
Felix Martinez-Rios
35002759
1 2 Ju l 2 01 7 Percolation and Phase Transition in SAT
Erdos and Renyi proved in 1960 that a drastic change occurs in a large random graph when the number of edges is half the number of nodes: a giant connected component surges. This was the origin of percolation theory, where statistic mechanics and mean field techniques are applied to study the behavior of graphs and other structures when we remove edges randomly. In the 90's the study of random SAT instances started. It was proved that in large 2 SAT random instances also a drastic change occurs when the number of clauses is equal to the number of variables: the formula almost surely changes from satisfiable to unsatisfiable. The same effect, but at distinct clause/variable ratios, was detected in k SAT and other random models. In this paper we study the relation between both phenomena, and establish a condition that allows us to easily find the phase transition threshold in several models of 2 SAT formulas. In particular, we prove the existence of a phase transition threshold in scale free random 2 SAT formulas.
Jordi Levy
16347357
Shifting the Phase Transition Threshold for Random Graphs and 2 SAT using Degree Constraints
We show that by restricting the degrees of the vertices of a graph to an arbitrary set \Delta the threshold point \alpha(\Delta) of the phase transition for a random graph with n vertices and m \alpha(\Delta) n edges can be either accelerated (e.g. \alpha(\Delta) \approx 0.381 for \Delta {0,1,4,5\ or postponed (e.g. \alpha( 2^0, 2^1, \cdots, 2^k, \cdots \approx 0.795 compared to a classical Erdos Renyi random graph with \alpha(\mathbb Z_{\geq 0} \tfrac12 In particular, we prove that the probability of graph being nonplanar and the probability of having a complex component, goes from 0 to 1 as m passes \alpha(\Delta) n We investigate these probabilities and also different graph statistics inside the critical window of transition (diameter, longest path and circumference of a complex component)
ArXiv
Sergey Dovgal Vlady Ravelomanana
15655007
The condensation phase transition in the regular k SAT model
Much of the recent work on random constraint satisfaction problems has been inspired by ingenious but non rigorous approaches from physics. The physics predictions typically come in the form of distributional fixed point problems that are intended to mimic Belief Propagation, a message passing algorithm, applied to the random CSP. In this paper we propose a novel method for harnessing Belief Propagation directly to obtain a rigorous proof of such a prediction, namely the existence and location of a condensation phase transition in the random regular $k$ SAT model.
APPROX RANDOM
Victor Bapst Amin Coja-Oghlan