Biased random k‐SAT

DOI10.1002/RSA.20996MaRDI QIDQ6074657zbMATH OpenFDO

Authors Joel Larsson, Klas Markström

Publication date 12 October 2023

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

combinatorial probabilityphase transitionrandom \(k\)-SATrandom constraint satisfaction problem

Mathematics Subject Classification ID

Combinatorial probability (60C05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational aspects of satisfiability (68R07)

Abstract: The basic random $k$-SAT problem is: Given a set of $n$ Boolean variables, and $m$ clauses of size $k$ picked uniformly at random from the set of all such clauses on our variables, is the conjunction of these clauses satisfiable? Here we consider a variation of this problem where there is a bias towards variables occurring positive -- i.e. variables occur negated w.p. $0<p<frac12$ and positive otherwise -- and study how the satisfiability threshold depends on $p$. For $p<frac12$ this model breaks many of the symmetries of the original random $k$-SAT problem, e.g. the distribution of satisfying assignments in the Boolean cube is no longer uniform. For any fixed $k$, we find the asymptotics of the threshold as $p$ approaches $0$ or $frac12$. The former confirms earlier predictions based on numerical studies and heuristic methods from statistical physics.

Recommendations

• Theory and Applications of Satisfiability Testing
• Going after the k-SAT threshold
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The asymptotic k-SAT threshold
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))

Cites work

• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• A note on random \(k\)-SAT for moderately growing \(k\)
• Balanced max 2-sat might not be the hardest
• Balls and bins: A study in negative dependence
• Critical behavior in the computational cost of satisfiability testing
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Differential equations for random processes and random graphs
• Entropy of theK-Satisfiability Problem
• scientific article; zbMATH DE number 3489128 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 195103 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• Lower bounds for random 3-SAT via differential equations
• Many hard examples for resolution
• On the critical percolation probabilities
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Proof of the satisfiability conjecture for large k
• Random 2-SAT with prescribed literal degrees
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Random k-SAT: A tight threshold for moderately growing k
• Sharp thresholds of graph properties, and the k-sat problem
• Speed and concentration of the covering time for structured coupon collectors
• Spines of random constraint satisfaction problems: definition and connection with computational complexity
• The asymptotic \(k\)-SAT threshold
• The high temperature case for the random K-sat problem
• The scaling window of the 2-SAT transition
• Theory and Applications of Satisfiability Testing

Cited in

(4)

• Biased landscapes for random constraint satisfaction problems
• Theory and Applications of Satisfiability Testing
• Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion
• Polarised random k-SAT

This page was built for publication: Biased random k‐SAT

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