Branching process approach for 2-SAT thresholds

DOI10.1239/JAP/1285335410MaRDI QIDQ4933200zbMATH OpenOpenAlexFDO

Authors Elchanan Mossel, Arnab Sen

Publication date 12 October 2010

Published in Journal of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

2-SATphase transitionsatisfiabilitytwo-type branching process

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: It is well known that, as $n$ tends to infinity, the probability of satisfiability for a random 2-SAT formula on $n$ variables, where each clause occurs independently with probability $alpha/2n$, exhibits a sharp threshold at $alpha=1$. We study a more general 2-SAT model in which each clause occurs independently but with probability $alph{a}_i/2n$ where $iin0,1,2$ is the number of positive literals in that clause. We generalize branching process arguments by Verhoeven(99) to determine the satisfiability threshold for this model in terms of the maximum eigenvalue of the branching matrix.

Recommendations

• A threshold for unsatisfiability
• A threshold for unsatisfiability
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• A remark on random 2-SAT
• A sharp threshold for a random constraint satisfaction problem

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A new look at survey propagation and its generalizations
• A threshold for unsatisfiability
• Correlation inequalities on some partially ordered sets
• Counting independent sets up to the tree threshold
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 2001586 (Why is no real title available?)
• Limit theorems for decomposable multi-dimensional Galton-Watson processes
• On the hardness of sampling independent sets beyond the tree threshold
• On the satisfiability threshold of formulas with three literals per clause
• On the solution-space geometry of random constraint satisfaction problems
• Random 2-SAT and unsatisfiability
• Random 2-SAT with prescribed literal degrees
• Random graphs.
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• Sharp thresholds of graph properties, and the k-sat problem
• The (2) limit in the random assignment problem
• The complexity of theorem-proving procedures
• The Forwarding Indices of Random Graphs
• The probabilistic analysis of a greedy satisfiability algorithm
• The scaling window of the 2-SAT transition
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Threshold values of random K‐SAT from the cavity method

This page was built for publication: Branching process approach for 2-SAT thresholds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933200)