Approximating the unsatisfiability threshold of random formulas

DOI<253::AID-RSA3>3.0.CO;2-U 10.1002/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-UzbMath0936.68038OpenAlexW2000931246MaRDI QIDQ4240602

Yannis C. Stamatiou, Lefteris M. Kirousis, Danny Krizanc, Evangelos Kranakis

Publication date: 3 May 2000

Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(199805)12:3<253::aid-rsa3>3.0.co;2-u

zbMATH Keywords

3-SATrandom Boolean formula

Mathematics Subject Classification ID

Related Items (43)

Phase transitions in discrete structures ⋮ On the solution‐space geometry of random constraint satisfaction problems ⋮ An improved upper bound on the non-3-colourability threshold ⋮ The Number of Satisfying Assignments of Random Regulark-SAT Formulas ⋮ On threshold properties of \(k\)-SAT: An additive viewpoint ⋮ Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ The unsatisfiability threshold revisited ⋮ The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘) ⋮ Regular random \(k\)-SAT: Properties of balanced formulas ⋮ Unnamed Item ⋮ Proof of the satisfiability conjecture for large \(k\) ⋮ A fast parallel SAT-solver -- efficient workload balancing ⋮ Maximum independent sets on random regular graphs ⋮ Counting Solutions to Random CNF Formulas ⋮ Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ Small maximal matchings in random graphs. ⋮ The asymptotic \(k\)-SAT threshold ⋮ On good algorithms for determining unsatisfiability of propositional formulas ⋮ On the average similarity degree between solutions of random \(k\)-SAT and random CSPs. ⋮ The cook-book approach to the differential equation method ⋮ Phase transitions of contingent planning problem ⋮ The scaling window of the 2-SAT transition ⋮ Satisfiability threshold for power law random 2-SAT in configuration model ⋮ A NEW UPPER BOUND FOR RANDOM (2 + p)-SAT BY FLIPPING TWO VARIABLES ⋮ On the satisfiability threshold and clustering of solutions of random 3-SAT formulas ⋮ An asymptotic expansion for theq-binomial series using singularity analysis for generating functions ⋮ Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT ⋮ Solution clustering in random satisfiability ⋮ On the satisfiability threshold of formulas with three literals per clause ⋮ Rigorous results for random (\(2+p)\)-SAT ⋮ Upper bounds on the satisfiability threshold ⋮ Satisfiability threshold for random regular \textsc{nae-sat} ⋮ PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS ⋮ Unnamed Item ⋮ Estimating satisfiability ⋮ Super solutions of random \((3 + p)\)-SAT ⋮ When does the giant component bring unsatisfiability? ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ Resolution complexity of random constraint satisfaction problems: Another half of the story ⋮ Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story ⋮ Selecting Complementary Pairs of Literals ⋮ A model of random industrial SAT

This page was built for publication: Approximating the unsatisfiability threshold of random formulas