A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
From MaRDI portal
Publication:4360139
DOI10.1006/jagm.1997.0867zbMath0883.68065OpenAlexW2078137578MaRDI QIDQ4360139
Yacine Boufkhad, Olivier Dubois
Publication date: 20 October 1997
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1997.0867
Related Items (26)
Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT ⋮ On the solution‐space geometry of random constraint satisfaction problems ⋮ On threshold properties of \(k\)-SAT: An additive viewpoint ⋮ The unsatisfiability threshold revisited ⋮ The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘) ⋮ Random k -SAT and the power of two choices ⋮ Regular random \(k\)-SAT: Properties of balanced formulas ⋮ Unnamed Item ⋮ An efficient approach to solving random \(k\)-SAT problems ⋮ Biased random k‐SAT ⋮ New Results on the Phase Transition for Random Quantified Boolean Formulas ⋮ On good algorithms for determining unsatisfiability of propositional formulas ⋮ The scaling window of the 2-SAT transition ⋮ Satisfiability threshold for power law random 2-SAT in configuration model ⋮ On the satisfiability threshold and clustering of solutions of random 3-SAT formulas ⋮ Pairs of SAT-assignments in random Boolean formulæ ⋮ Solution clustering in random satisfiability ⋮ On the satisfiability threshold of formulas with three literals per clause ⋮ Rigorous results for random (\(2+p)\)-SAT ⋮ Random 2-SAT: Results and problems ⋮ Upper bounds on the satisfiability threshold ⋮ Estimating satisfiability ⋮ Length of prime implicants and number of solutions of random CNF formulae ⋮ Exact location of the phase transition for random (1,2)-QSAT ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ Selecting Complementary Pairs of Literals
This page was built for publication: A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
