The scaling window of the 2-SAT transition

DOI10.1002/rsa.1006zbMath0979.68053arXivmath/9909031OpenAlexW2006424894WikidataQ56288406 ScholiaQ56288406MaRDI QIDQ2725029

Béla Bollobás, Jeong Han Kim, Jennifer T. Chayes, Christian Borgs, David Bruce Wilson

Publication date: 19 February 2002

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/9909031

zbMATH Keywords

random 2-satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80)

Related Items

A sharp threshold in proof complexity yields lower bounds for satisfiability search, Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability, Lower and Upper Bounds for Random Mimimum Satisfiability Problem, On threshold properties of \(k\)-SAT: An additive viewpoint, The state of SAT, Phase transition in a random NK landscape model, Threshold for monotone symmetric properties through a logarithmic Sobolev inequality, Random k -SAT and the power of two choices, Proof of the satisfiability conjecture for large \(k\), Maximum independent sets on random regular graphs, The scaling window of the model \(d\)-\(k\)-CSP, The number of satisfying assignments of random 2‐SAT formulas, Biased random k‐SAT, An upper (lower) bound for Max (Min) CSP, One-step replica symmetry breaking of random regular NAE-SAT. II, Generalized satisfiability problems: Minimal elements and phase transitions., Exact enumeration of satisfiable 2-SAT formulae, Random 2 XORSAT phase transition, Critical window of the symmetric perceptron, A tighter upper bound for random MAX \(2\)-SAT, Threshold behaviors of a random constraint satisfaction problem with exact phase transitions, The Satisfiability Threshold fork-XORSAT, Algorithms for computing minimal equivalent subformulas, Computational complexity of auditing finite attributes in statistical databases, Dynamics of random graphs with bounded degrees, Hypercube percolation, Finite size scaling for the core of large random hypergraphs, The phase transition in the uniformly grown random graph has infinite order, D?E?K=(1000)8, Random maps, coalescing saddles, singularity analysis, and Airy phenomena, Phase transition and finite-size scaling for the integer partitioning problem, Recognizing frozen variables in constraint satisfaction problems, Branching Process Approach for 2-Sat Thresholds, An Upper Bound on the Space Complexity of Random Formulae in Resolution, Arbitrary Threshold Widths for Monotone, Symmetric Properties, Statistical mechanics methods and phase transitions in optimization problems, Upper bounds on the satisfiability threshold, Bounding the scaling window of random constraint satisfaction problems, Satisfiability threshold for random regular \textsc{nae-sat}, Random 2-XORSAT at the Satisfiability Threshold, On the probability of planarity of a random graph near the critical point, Exact location of the phase transition for random (1,2)-QSAT, When does the giant component bring unsatisfiability?, Typical case complexity of satisfiability algorithms and the threshold phenomenon, An Empirical Study of MAX-2-SAT Phase Transitions, The number of 2-SAT functions, A model of random industrial SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Some simplified NP-complete graph problems
• Correlation inequalities on some partially ordered sets
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Random 2-SAT and unsatisfiability
• A remark on random 2-SAT
• Counting the number of solutions for instances of satisfiability
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• The transitive closure of a random digraph
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• The number of connected sparsely edged graphs. III. Asymptotic results
• Many hard examples for resolution
• The Evolution of Random Graphs
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• On the random graph structure near the critical point
• Component behavior near the critical point of the random graph process
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• The number of connected sparsely edged graphs
• Approximating the unsatisfiability threshold of random formulas
• Sharp thresholds of graph properties, and the $k$-sat problem
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• Entropy of theK-Satisfiability Problem
• Bounding the unsatisfiability threshold of random 3-SAT
• Tail bounds for occupancy and the satisfiability threshold conjecture
• On Random 3-sat
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Families of Non-disjoint subsets
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• The birth of the infinite cluster: Finite-size scaling in percolation