Query: The SAT phase transition

title: The SAT Phase Transition
abstract: 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.

title: The SAT phase transition
abstract: 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.

title: Observed Lower Bounds for Random 3 SAT Phase Transition Density Using Linear Programming
abstract: 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  and even than that of the greedy algorithm 3.52) proposed by Kaporis

title: On the Empirical Time Complexity of Scale Free 3 SAT at the Phase Transition
abstract: 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.

title: Phase Transition in Realistic Random SAT Models
abstract: 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.

title: Percolation and Phase Transition in SAT
abstract: 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.

title: 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.

title: 1 2 Ju l 2 01 7 Percolation and Phase Transition in SAT
abstract: 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.

title: Shifting the Phase Transition Threshold for Random Graphs and 2 SAT using Degree Constraints
abstract: 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)

title: The condensation phase transition in the regular k SAT model
abstract: 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.