A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae

DOI10.1006/JAGM.1997.0867MaRDI QIDQ4360139zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

\(r\)-SAT random formulae

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1114008
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• On the satisfiability threshold of formulas with three literals per clause

Cited in

(38)

• Approximating the Satisfiability Threshold for Random k-XOR-formulas
• The scaling window of the 2-SAT transition
• The unsatisfiability threshold revisited
• Exact location of the phase transition for random (1,2)-QSAT
• Super solutions of random \((3 + p)\)-SAT
• Lower and Upper Bounds for Random Mimimum Satisfiability Problem
• The maximum length of prime implicates for instances of 3-SAT
• Pairs of SAT-assignments in random Boolean formulæ
• An efficient approach to solving random \(k\)-SAT problems
• Typical case complexity of satisfiability algorithms and the threshold phenomenon
• On good algorithms for determining unsatisfiability of propositional formulas
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
• Solution clustering in random satisfiability
• On the satisfiability threshold of formulas with three literals per clause
• On threshold properties of k-SAT: An additive viewpoint
• Random k-SAT and the power of two choices
• Upper bounds on the satisfiability threshold
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$
• Rigorous results for random (2+p)-SAT
• New Results on the Phase Transition for Random Quantified Boolean Formulas
• Length of prime implicants and number of solutions of random CNF formulae
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• Biased random k‐SAT
• scientific article; zbMATH DE number 1369843 (Why is no real title available?)
• On the solution-space geometry of random constraint satisfaction problems
• Random k-sat: the limiting probability for satisfiability for moderately growing k
• Estimating satisfiability
• Regular random \(k\)-SAT: Properties of balanced formulas
• Random 2-SAT: Results and problems
• Non uniform selection of solutions for upper bounding the 3-SAT threshold
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
• Satisfiability threshold for power law random 2-SAT in configuration model
• Selecting Complementary Pairs of Literals
• Satisfiability threshold for power law random 2-SAT in configuration model
• Threshold properties of random Boolean constraint satisfaction problems
• Bounding the unsatisfiability threshold of random 3-SAT

This page was built for publication: A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae

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