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 (47)

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

This page was built for publication: The scaling window of the 2-SAT transition